[蓝桥杯2015决赛]穿越雷区（BFS求最短路）

题目描述

X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？
已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。
例如：

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

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

输入

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

输出

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

样例输入 Copy

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

样例输出 Copy

思路：也就利用bfs，要穿越不同的雷区，-，+，所以也就相当于当前的这个的值不和前面穿过的一个值相同。  1 #include <iostream>
  2 #include <queue>
  3 using namespace std;
  4 constexpr size_t maxn = 2005;
  5 struct node{
  6 	int x,y;
  7 	int last;
  8 	int step;
  9 	node(int x, int y, int last):x(x), y(y), last(last),step(0){}
 10 };
 11 bool book[maxn][maxn];
 12 int s1, s2, n;
 13 int mp[maxn][maxn];
 14 int ans;
 15 queue<node> q;
 16 bool judge(int x, int y)
 17 {
 18 	return x >= 0 && x < n && y >= 0 && y < n;
 19 }
 20 void bfs(){
 21 
 22 	while(q.size()){
 23 		node p = q.front();
 24 		q.pop();
 25 		if(mp[p.x][p.y] == 4){
 26 			cout << p.step << endl;
 27 			return;
 28 		}
 29 
 30 		for(int i = -1; i <= 1; ++ i){
 31 			for(int j = -1; j <= 1; ++ j){
 32 				if(abs(i) == abs(j))continue;
 33 				node p2 = p;
 34 				p2.x = p2.x + i;
 35 				p2.y = p2.y + j;
 36 				if(judge(p2.x,p2.y) && !book[p2.x][p2.y] && p2.last != mp[p2.x][p2.y]){
 37 					p2.last = mp[p2.x][p2.y];
 38 					p2.step++;
 39 					book[p2.x][p2.y] = true;
 40 					q.push(p2);
 41 				}
 42 			}
 43 		}
 44 
 45 	}
 46 	cout << -1 << endl;
 47 }
 48 
 49 
 50 
 51 int main(){
 52 
 53 	char a;
 54 	cin >> n;
 55 
 56 	for(int i = 0; i < n; ++ i){
 57 		for(int j = 0; j < n; ++ j){
 58 			cin >> a;
 59 			if(a == 'A'){
 60 				mp[i][j] = 3;
 61 				s1 = i, s2 = j;
 62 			}
 63 			if(a == 'B')
 64 				mp[i][j] = 4;
 65 			if(a == '-')
 66 				mp[i][j] = 0;
 67 			if(a == '+')
 68 				mp[i][j] = 1;
 69 		}
 70 	}
 71 	q.push({s1,s2,3});
 72 	book[s1][s2] = true;
 73 	bfs();
 74 }

追求吾之所爱