拯救天使 (BFS)

  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 }