#include<stdio.h> #include<string.h> char maze[42][42]; int s_l,s_r,e_l,e_r,w,h,s_f; vist[42][42]; struct queue {
int line,row,depth; }queue[1603]; int work_l() { int i,j,l,r; l=s_l; r=s_r; j=s_f; for(i=1;;i++) { if(r==e_r && l==e_l) break; if(j==0) { if(maze[l-1][r]=='.'){l--;j=3;continue;} else if(maze[l][r+1]=='.'){r++;continue;} else if(maze[l+1][r]=='.'){l++;j=1;continue;} else {r--;j=2;continue;} } else if(j==1) { if(maze[l][r+1]=='.'){r++;j=0;continue;} else if(maze[l+1][r]=='.'){l++;continue;} else if(maze[l][r-1]=='.'){r--;j=2;continue;} else {l--;j=3;continue;} } else if(j==2) { if(maze[l+1][r]=='.'){l++;j=1;continue;} else if(maze[l][r-1]=='.'){r--;continue;} else if(maze[l-1][r]=='.'){l--;j=3;continue;} else {r++;j=0;continue;} } else { if(maze[l][r-1]=='.'){r--;j=2;continue;} else if(maze[l-1][r]=='.'){l--;continue;} else if(maze[l][r+1]=='.'){r++;j=0;continue;} else {l++;j=1;continue;} } } return i; } int work_r() { int i,j,l,r; l=s_l; r=s_r; j=s_f; for(i=1;;i++) { if(r==e_r && l==e_l) break; if(j==0) { if(maze[l+1][r]=='.'){l++;j=1;continue;} else if(maze[l][r+1]=='.'){r++;continue;} else if(maze[l-1][r]=='.'){l--;j=3;continue;} else {r--;j=2;continue;} } else if(j==1) { if(maze[l][r-1]=='.'){r--;j=2;continue;} else if(maze[l+1][r]=='.'){l++;continue;} else if(maze[l][r+1]=='.'){r++;j=0;continue;} else {l--;j=3;continue;} } else if(j==2) { if(maze[l-1][r]=='.'){l--;j=3;continue;} else if(maze[l][r-1]=='.'){r--;continue;} else if(maze[l+1][r]=='.'){l++;j=1;continue;} else {r++;j=0;continue;} } else { if(maze[l][r+1]=='.'){r++;j=0;continue;} else if(maze[l-1][r]=='.'){l--;continue;} else if(maze[l][r-1]=='.'){r--;j=2;continue;} else {l++;j=1;continue;} } } return i; } int BFS() { int tail=1,head=1,r,l,i=1; l=s_l;r=s_r; queue[1].line=s_l; queue[1].row=s_r; queue[1].depth=1; memset(vist,0,sizeof(vist)); //vist[queue[1].line][queue[1].row]=1; while(head<=tail) { // i++; //if(vist[queue[head].line][queue[head].row]!=1)//我在这条语句快疯掉了,加了这条语句就tle,TMD~~ // { //不加就0ms~~~ if(queue[head].line==e_l && queue[head].row==e_r)//准确来说是一入队列就将vist标记为1(这是对的),还是出队时才标记1(这是错的) return queue[head].depth; //vist[queue[head].line][queue[head].row]=1; l=queue[head].line;r=queue[head++].row; if(vist[l][r-1]==0 && maze[l][r-1]=='.'){queue[++tail].line=l;vist[l][r-1]=1;queue[tail].row=r-1;queue[tail].depth=queue[head-1].depth+1;} if(vist[l-1][r]==0 && maze[l-1][r]=='.'){queue[++tail].line=l-1;vist[l-1][r]=1;queue[tail].row=r;queue[tail].depth=queue[head-1].depth+1;} if(vist[l][r+1]==0 && maze[l][r+1]=='.'){queue[++tail].line=l;vist[l][r+1]=1;queue[tail].row=r+1;queue[tail].depth=queue[head-1].depth+1;} if(vist[l+1][r]==0 && maze[l+1][r]=='.'){queue[++tail].line=l+1;vist[l+1][r]=1;queue[tail].row=r;queue[tail].depth=queue[head-1].depth+1;} // } } } int main() { int T; int i,j; scanf("%d",&T); while(T--) { scanf("%d%d",&w,&h); // memset(maze,'\0',sizeof(maze)); for(i=1;i<=h;i++) { getchar(); for(j=1;j<=w;j++) { scanf("%c",&maze[i][j]); if(maze[i][j]=='S') { s_l=i; s_r=j; maze[i][j]='.'; } else if(maze[i][j]=='E') { e_l=i; e_r=j; maze[i][j]='.'; } } } if(s_l==1) s_f=1; else if(s_r==1) s_f=0; else if(s_l==h) s_f=3; else s_f=2; printf("%d %d %d\n",work_l(),work_r(),BFS()); } return 0; }
这道只是很简单的BFS搜索题,但是我却被困了一天一夜,TMD,唉,还是练得不够哦~~