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