蓝桥杯穿越雷区(bfs)

题目描述

X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。
例如：
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

坦克车只能水平或垂直方向上移动到相邻的区。

输入

输入第一行是一个整数n，表示方阵的大小， 4<=n<100
接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。
A，B都只出现一次。

输出

要求输出一个整数，表示坦克从A区到B区的最少移动步数。
如果没有方案，则输出-1

样例输入

5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

样例输出

 1 #include<iostream>
 2 #include<queue>
 3 
 4 using namespace std;
 5 
 6 struct node
 7 {
 8     char ch;    // 该坐标处的字符 
 9     int x, y;    // 在地图上的坐标 
10     int step;    // 步数(层数) 
11 }nod;
12 
13 char mp[110][110];
14 int vis[110][110];
15 int dx[4] = {1,-1,0,0};
16 int dy[4] = {0,0,1,-1};
17 int n;
18 int start_x, start_y;
19 int flag = 0;
20 
21 void bfs(int x, int y)
22 {
23     vis[x][y] = 1;
24     queue<node>Q;
25     nod.step = 0;
26     nod.x = x;
27     nod.y = y;
28     nod.ch = 'A';
29     Q.push(nod);
30     
31     node t, p;
32     while(!Q.empty())
33     {
34         t = Q.front();
35         Q.pop();
36         
37         if(t.ch == 'B')
38         {
39             flag = 1;
40             cout << t.step << endl;
41             return;
42         }
43         
44         for(int i = 0; i < 4; ++i)
45         {
46             int xx = t.x + dx[i];
47             int yy = t.y + dy[i];
48             
49             if(xx >= 0 && yy >= 0 && xx < n && yy < n && !vis[xx][yy] && mp[xx][yy] != t.ch) // 这一层的字符不能和前一层的一样，否则坦克会报废 
50             {
51                 p.ch = mp[xx][yy];
52                 p.x = xx;
53                 p.y = yy;
54                 p.step = t.step + 1;
55                 Q.push(p);
56             }
57         }
58     
59     }
60     
61     cout << -1 << endl;        // 队列已经空了仍然没有找到方案，则输出-1 
62     
63 }
64 
65 int main()
66 {
67     cin >> n;
68     for(int i = 0; i < n; ++i)
69         for(int j = 0; j < n; ++j)
70         {
71             cin >> mp[i][j];
72             if(mp[i][j] == 'A')
73             {
74                 start_x = i;
75                 start_y = j;
76             }
77         }    
78             
79      bfs(start_x, start_y);
80 
81     return 0;
82 }

蓝桥杯 穿越雷区(bfs)

蓝桥杯穿越雷区(bfs)