http://ybt.ssoier.cn:8088/problem_show.php?pid=1256
1 #include<bits/stdc++.h> 2 using namespace std; 3 int t, row, col; 4 char mp[205][205]; 5 int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};//定义四个方向 6 struct node{//结构体定义位置和步数 7 int x, y, s; 8 }; 9 node que[40010];//结构体数组定义队列 10 int f, r;//队首队尾 11 int sx, sy, ex, ey;//定义初始位置和目标位置 12 void pr()//测试使用 29行 13 { 14 cout<<"--------------"<<endl; 15 for(int i=0; i<row; i++){ 16 for(int j=0; j<col; j++){ 17 cout<<mp[i][j]; 18 } 19 cout<<endl; 20 } 21 } 22 int bfs(){ 23 int ret=0;//返回步数 24 f=r=1;//队列初始化 25 mp[sx][sy]='#';//更改初始位置 26 que[r].x=sx; que[r].y=sy; que[r].s=0;//初始位置入队 27 while(f<=r){ 28 int fx=que[f].x, fy=que[f].y, fs=que[f].s;//获取队首信息 29 // pr(); 30 // cout<<endl<<fs<<endl; 31 if(fx==ex && fy==ey){//判断是否找到目标 32 ret=fs; 33 break; 34 } 35 for(int i=0; i<4; i++){ 36 int nx=fx+dir[i][0]; 37 int ny=fy+dir[i][1]; 38 if(nx>=0 && nx<row && ny>=0 && ny<col && (mp[nx][ny]=='.' || mp[nx][ny]=='E')){//注意限制条件 39 mp[nx][ny]='#'; 40 r++;//队尾位置后移准备入队 41 que[r].x=nx;//入队 42 que[r].y=ny; 43 que[r].s=fs+1; 44 } 45 } 46 f++; 47 } 48 return ret; 49 } 50 int main() 51 { 52 cin>>t; 53 while(t--){ 54 cin>>row>>col; 55 for(int i=0; i<row; i++)cin>>mp[i]; 56 for(int i=0; i<row; i++){ 57 for(int j=0; j<col; j++){ 58 if(mp[i][j]=='S')sx=i, sy=j; 59 if(mp[i][j]=='E')ex=i, ey=j; 60 } 61 } 62 int ans=bfs(); 63 if(ans)cout<<ans<<endl; 64 else cout<<"oop!"<<endl; 65 } 66 return 0; 67 }