拯救天使 (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 }