TMDTMD
IDA*没跑了。什么是IDA*？
就是迭代深搜+A*估个价。
然而为什么调了一天？
n<=2的时候我输出了东西。。。。
看了一天。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 15 #define inf 2000000000 using namespace std; int n,map[maxn][maxn],tot=0,dis[maxn][maxn],mx=0,ans[maxn*maxn*maxn],d,dr[maxn][maxn]; int dx[]={0,0,-1,1,0},dy[]={0,1,0,0,-1}; char s[maxn]; queue <int> q; struct point { int x,y; point (int x,int y):x(x),y(y) {} point () {} }p[maxn*maxn]; bool bnd(int x,int y) { if ((x==1) || (x==n) || (y==1) || (y==n)) return true; return false; } bool judge(int x,int y) { if ((x>=1) && (x<=n) && (y>=1) && (y<=n)) return true; return false; } int bfs(int x,int y) { for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dr[i][j]=inf; while (!q.empty()) q.pop(); dr[x][y]=0;q.push(x);q.push(y); while (!q.empty()) { int hx,hy; hx=q.front();q.pop();hy=q.front();q.pop(); if (bnd(hx,hy)) return dr[hx][hy]; for (int i=1;i<=4;i++) { int tx=hx+dx[i],ty=hy+dy[i]; if ((map[tx][ty]) && (dr[tx][ty]==inf) && (judge(tx,ty))) { q.push(tx);q.push(ty); dr[tx][ty]=dr[hx][hy]+1; } } } return inf; } int gets_h(point p[]) { int mx=0; for (int i=1;i<=tot;i++) mx=max(mx,dis[p[i].x][p[i].y]); return mx; } point modify(point x,int y) { if (bnd(x.x,x.y)) return x; point now=point(x.x+dx[y],x.y+dy[y]); if ((!map[now.x][now.y]) || (!judge(now.x,now.y))) return x; else return now; } bool IDA(int deep,point p[]) { point node[maxn*maxn]; if (gets_h(p)+deep>d) return false; if (deep==d) return true; for (int i=1;i<=4;i++) { ans[deep]=i; for (int j=1;j<=tot;j++) node[j]=modify(p[j],i); if (IDA(deep+1,node)) return true; } return false; } void work() { tot=0;memset(ans,0,sizeof(ans)); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dis[i][j]=-1; for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=1;j<=n;j++) { if (s[j-1]=='0') map[i][j]=1; else map[i][j]=0; if ((map[i][j]) && (!bnd(i,j))) p[++tot]=point(i,j); } } if (!tot) return; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if (!map[i][j]) dis[i][j]=inf; else { if (bnd(i,j)) dis[i][j]=0; else dis[i][j]=bfs(i,j); mx=max(mx,dis[i][j]); if (dis[i][j]==inf) {printf("CX_naive ");return;} } } for (d=1;;d++) { if (IDA(0,p)) { for (int j=0;j<d;j++) { if (ans[j]==1) printf("east "); else if (ans[j]==2) printf("north "); else if (ans[j]==3) printf("south "); else if (ans[j]==4) printf("west "); } return; } } } int main() { int ret=0; while (scanf("%d",&n)!=EOF) { if (ret++) printf(" "); work(); } return 0; }