HDU 1813 Escape from Tetris IDA*搜索

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

DEBUG到死啊，先后不断出现TLE,WA等错误。

首先这是个好题。开始完全没有思路啊。

先预处理每个点到边界的最短距离，这样就可以构造估价函数，也就是所有点到边界最短距离的最大值，也就有了A*剪枝。状态还是很多的，而且不方便HASH，所以肯定是使用迭代加深搜索，最终就是IDA*了。

minval[][]表示每个点到边界的最短距离，由BFS生成。

第一次提交是TLE,很郁闷，这个A*剪枝是很给力的，后来发现我的BFS是从所有点开始，都跑一遍BFS，效率太慢。可以从边界出发，BFS，这样就可以利用之前的结果进行剪枝。

再次提交还是TLE，结果YY了一组数据，发现意外终止，这样的情况怎么会判TLE,而不是RE呢，郁闷

在IDA*的时候，只需要判断中间的非‘1’的点，于是一开始就把点加入vector，直接传参，就不需要判断每一个点，

void IDAstar(vector<Node>b,int tmp_depth,int father)

结果这个函数，有一组数组，在深度为6的时候，一调用直接挂了，也许是因为递归内存太大，爆了。

于是又YY成了数组，结果提交是WA，发现的确有问题，数组开小了。。各种郁闷

#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<string>#include<vector>#include<algorithm>#include<map>#include<set>#define inf 1<<30using namespace std;int n,minval[10][10];char str[10][10];int depth;bool flag;int ans[1000];int pre[4]={3,2,1,0};int way[4][2]={{0,1},{-1,0},{1,0},{0,-1}};struct Node{int x,y;bool check(){if(x>=0&&x<n&&y>=0&&y<n)return true;return false;}}tmp,u,v;int x[100],y[100],cnt;bool isok(int x,int y){if(x==0||x==n-1||y==0||y==n-1)return true;return false;}void bfs(Node s){queue<Node>que;while(!que.empty())que.pop();que.push(s);minval[s.x][s.y]=0;while(!que.empty()){u=que.front();que.pop();for(int i=0;i<4;i++){v=u;v.x+=way[i][0];v.y+=way[i][1];if(v.check()&&str[v.x][v.y]=='0'){if(minval[v.x][v.y]<=minval[u.x][u.y]+1)continue;minval[v.x][v.y]=minval[u.x][u.y]+1;que.push(v);}}}}int get_h(int *t_x,int *t_y){int res=0;for(int i=0;i<cnt;i++)res=max(res,minval[t_x[i]][t_y[i]]);return res;}void IDAstar(int *t_x,int *t_y,int tmp_depth){if(flag)return;if(get_h(t_x,t_y)>tmp_depth)return;if(tmp_depth==0){flag=true;return;}for(int i=0;i<4;i++){if(flag)return;int X[100],Y[100];for(int j=0;j<cnt;j++){X[j]=t_x[j];Y[j]=t_y[j];if(isok(X[j],Y[j]))continue;if(str[X[j]+way[i][0]][Y[j]+way[i][1]]=='0'){X[j]+=way[i][0];Y[j]+=way[i][1];}}ans[tmp_depth]=i;IDAstar(X,Y,tmp_depth-1);}}int main(){int cas=0;while(scanf("%d",&n)!=EOF){if(cas++)printf("\n");for(int i=0;i<n;i++) scanf("%s",&str[i]);cnt=0;flag=false;for(int i=0;i<n;i++)for(int j=0;j<n;j++)minval[i][j]=inf;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(str[i][j]=='0'){tmp.x=i;tmp.y=j;if(!isok(i,j)){x[cnt]=i;y[cnt++]=j;}elsebfs(tmp);}}}if(cnt==0)continue;for(depth=get_h(x,y);;depth++){IDAstar(x,y,depth);if(flag){for(int i=depth;i>0;i--)switch(ans[i]){case 0:printf("east\n");break;case 3:printf("west\n");break;case 2:printf("south\n");break;case 1:printf("north\n");break;}break;}}}return 0;}