1256:献给阿尔吉侬的花束

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  } 

 

上一篇:新手入门 : Windows Phone 8.1 开发 视频学习地址


下一篇:1729石子合并问题(DP)