就是搜。
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 22
int fang[][]={{,},{,},{,-},{-,}};
int map[maxn][maxn],vis[maxn][maxn][][],n;
struct node
{
int count;//计数
int way;//方向
int x;
int y;
int flag;//是否拿到金子
};
int ok(int x,int y)
{
if(x<||x>=n||y<||y>=n||map[x][y]==||map[x][y]==)
return ;
return ;
}
int bfs()
{
int i,j;
queue<node>q;
node temp,t;
memset(vis,,sizeof(vis));
temp.x=temp.y=temp.flag=temp.count=;
temp.way=;
q.push(temp);
vis[][][][]=;
while(!q.empty())
{
temp=q.front();
q.pop();
if(temp.count>)
return -;
if(map[temp.x][temp.y]==&&!temp.flag)
{
temp.count++;
temp.flag=;
vis[temp.x][temp.y][temp.way][temp.flag]=;
q.push(temp);
continue;
}
if(temp.x==&&temp.y==&&temp.flag)
{
return temp.count+;
}
for(i=-;i<;i++)
{
if(i==)
{
t.count=temp.count+;
t.flag=temp.flag;
t.way=temp.way;
t.x=temp.x+fang[t.way][];
t.y=temp.y+fang[t.way][];
}
else
{
t.count=temp.count+;
t.flag=temp.flag;
t.way=temp.way+i+;
t.way%=;
t.x=temp.x;
t.y=temp.y;
}
if(!vis[t.x][t.y][t.way][t.flag]&&ok(t.x,t.y))
{
vis[t.x][t.y][t.way][t.flag]=;
q.push(t);
}
}
}
return -;
}
int main()
{
int i,j,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(map,,sizeof(map));
while()
{
int x,y,z;
scanf("%d%d%d",&z,&x,&y);
if(z==-&&y==-&&x==-)
break;
map[x][y]=z;
}
if(map[][]==)
{
printf("-1\n");
continue;
}
int ans=bfs();
if(ans==-)
printf("-1\n");
else if(-*ans<)
printf("-1\n");
else
printf("%d\n",-*ans);
}
}
/*
1
2
3 1 1
-1 -1 -1
*/