题目：
| 1242 | Rescue |
1 //这是一个比较标准的bfs，没有经过任何优化，但是思路比较清晰，容易看懂。 2 #include <iostream> 3 #include <cstdio> 4 #include <queue> 5 using namespace std; 6 //node结构体 7 typedef struct 8 { 9 int x; 10 int y; 11 int len; 12 }node; 13 //全局变量定义 14 #define M 202 15 char Map[M][M];//地图 16 int mask[M][M];//访问标志 17 queue<node> q;//队列，只在bfs中用到 18 int bx,by,ex,ey,w,h;//起点、终点、宽、高 19 int step[4][2] = {//四个方向 20 //0-up 21 0,-1, 22 //1-right 23 1,0, 24 //2-down 25 0,1, 26 //3-left 27 -1,0 28 }; 29 30 void readMap(int m,int n);//读取地图 31 void bfs();//bfs 32 int tryXY(int x,int y);//尝试x、y点 33 34 void main() 35 { 36 while (scanf("%d %d",&h,&w)==2) 37 { 38 readMap(h,w); 39 bfs(); 40 cout<<mask[ex][ey]<<endl; 41 } 42 } 43 44 void readMap(int m,int n)//m-h,n-w 45 { 46 int i,j; 47 for (i=0;i<m;i++) 48 { 49 for (j=0;j<n;j++) 50 { 51 cin>>Map[i][j]; 52 mask[i][j] = -1;//标志为未访问 53 if (Map[i][j] == 'r') 54 {//friend为起点，且化为road 55 Map[i][j] = '.'; 56 bx = i; by = j; 57 } 58 if (Map[i][j] == 'a') 59 {//angel为终点，且化为road 60 Map[i][j] = '.'; 61 ex = i; ey = j; 62 } 63 } 64 } 65 } 66 67 void bfs() 68 { 69 node n,m;//m为队头，n为m衍生的测试点 70 int i,ret; 71 //起点 72 m.x = bx; 73 m.y = by; 74 m.len = 0;//len 75 mask[bx][by] = 0;//ask 76 q.push(m);//push 77 //处理 78 while (q.size()) 79 { 80 //get front 81 m = q.front(); 82 q.pop(); 83 //test node m 84 for (i=0 ; i<4 ; i++) 85 { 86 n.x = m.x+step[i][0]; n.y = m.y+step[i][1]; n.len = m.len+1; 87 ret = tryXY(n.x,n.y); 88 switch(ret) 89 { 90 case -1:// 91 break; 92 case 0: 93 case 1: 94 n.len += ret; 95 //如果为访问，保存花销；如果已经访问，保存花销最少。 96 if (mask[n.x][n.y] == -1 || n.len<mask[n.x][n.y]) 97 { 98 mask[n.x][n.y] = n.len;//已经访问且保存的是最小花销 99 q.push(n); 100 } 101 break; 102 } 103 } 104 105 } 106 } 107 int tryXY(int x,int y) 108 { 109 int ret; 110 //越界或遇到墙 111 if (!(x>=0 && x<w && y>=0 && y<h) || (Map[x][y] == '#')) 112 ret = -1; 113 //road or angel 114 if (Map[x][y] == '.') 115 ret = 0; 116 //guard 117 if (Map[x][y] == 'x') 118 ret = 1; 119 return ret; 120 }
