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=,dis[maxn][maxn],mx=,ans[maxn*maxn*maxn],d,dr[maxn][maxn];
int dx[]={,,-,,},dy[]={,,,,-};
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==) || (x==n) || (y==) || (y==n)) return true;
return false;
}
bool judge(int x,int y)
{
if ((x>=) && (x<=n) && (y>=) && (y<=n)) return true;
return false;
}
int bfs(int x,int y)
{
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
dr[i][j]=inf;
while (!q.empty()) q.pop();
dr[x][y]=;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=;i<=;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]+;
}
}
}
return inf;
}
int gets_h(point p[])
{
int mx=;
for (int i=;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=;i<=;i++)
{
ans[deep]=i;
for (int j=;j<=tot;j++) node[j]=modify(p[j],i);
if (IDA(deep+,node)) return true;
}
return false;
}
void work()
{
tot=;memset(ans,,sizeof(ans));
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
dis[i][j]=-;
for (int i=;i<=n;i++)
{
scanf("%s",s);
for (int j=;j<=n;j++)
{
if (s[j-]=='') map[i][j]=;
else map[i][j]=;
if ((map[i][j]) && (!bnd(i,j))) p[++tot]=point(i,j);
}
}
if (!tot) return;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
{
if (!map[i][j]) dis[i][j]=inf;
else
{
if (bnd(i,j)) dis[i][j]=;
else dis[i][j]=bfs(i,j);
mx=max(mx,dis[i][j]);
if (dis[i][j]==inf) {printf("CX_naive\n");return;}
}
}
for (d=;;d++)
{
if (IDA(,p))
{
for (int j=;j<d;j++)
{
if (ans[j]==) printf("east\n");
else if (ans[j]==) printf("north\n");
else if (ans[j]==) printf("south\n");
else if (ans[j]==) printf("west\n");
}
return;
}
}
}
int main()
{
int ret=;
while (scanf("%d",&n)!=EOF)
{
if (ret++) printf("\n");
work();
}
return ;
}