（蓝桥杯 2015 国）穿越雷区 （模拟 + bfs)

X 星的坦克战车很奇怪它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转否则将报废。某坦克需要从 A 区到 B 区去AB 区本身是安全区没有正能量或负能量特征怎样走才能路径最短已知的地图是一个方阵上面用字母标出了 AB 区其它区都标了正号或负号分别表示正负能量辐射区。例如A - - - - - - - - - B - -坦克车只能水平或垂直方向上移动到相邻的区。输入格式输入第一行是一个整数 n表示方阵的大小4≤n100。接下来是 n 行每行有 n 个数据可能是AB-中的某一个中间用空格分开。输出格式要求输出一个整数表示坦克从 A 区到 B 区的最少移动步数。如果没有方案则输出 −1。/////////////////////////////////////////////////////////////// 分割线 ///////////////////////////////////////////////////////////////////////上面是题目下面是小白也能看懂的 模拟 bfs 路线代码分成了三种情况来讨论也把起始位置考虑了进去一开始我们读取n,当遇到A的时候就是起始位置我们那变量保存一下Z就是最终位置也保存起来。需要一个bool类型的数组来标记该位置是否已经走过还有方向数组dxdy。当我们读取完毕之后我们会有起始位置和最终位置我们吧起始位置放入队列中就开始我们的bfs搜索。我们还需要走多少步我们定义一个pos变量来标记该层是第几层当我们到达了最终位置就直接返回该层数。反之返回-1这时候保存的是该起点位置的下标拿出下标看看该位置元素为- 、或者是A。#include bits/stdc.h using namespace std; char arr[102][102]; bool vis[102][102]; int dx[4] { 1, -1, 0, 0 }; int dy[4] { 0, 0, 1, -1 }; int main() { int n; cin n; int sx, sy, zx, zy; // 定义起始位置和最终位置 for(int i 1; i n; i) for(int j 1; j n; j) { cin arr[i][j]; char ch arr[i][j]; if(ch A) { sx i; sy j; // 起始位置 } if(ch B) { zx i; zy j; //最终位置 } } queuepairint, int q; // 定义一个存储下标的队列 q.push({sx, sy}); vis[sx][sy] true; int size 0; while(q.size()) { size; int zz q.size(); // 看看该步数下有多少个元素保留上次bfs的结果新加入的在下次循环中 for(int i 0; i zz; i) { pairint, int p q.front(); q.pop(); // 拿出队头元素 int a p.first, b p.second; char ch arr[a][b]; // 看该位置为什么 if(ch ) { for(int k 0; k 4; k) { int x a dx[k], y b dy[k]; // 确定下一步的位置 if(x 1 x n y 1 y n !vis[x][y]) { if(x zx y zy) { cout size; return 0; } else if(arr[x][y] -) { vis[x][y] true; q.push({x, y}); } } } } else if(ch -) { for(int k 0; k 4; k) { int x a dx[k], y b dy[k]; if(x 1 x n y 1 y n !vis[x][y]) { if(x zx y zy) { cout size; return 0; } else if(arr[x][y] ) { vis[x][y] true; q.push({x, y}); } } } } else { for(int k 0; k 4; k) { int x a dx[k], y b dy[k]; if(x 1 x n y 1 y n !vis[x][y]) { if(x zx y zy) { cout size; return 0; } else { vis[x][y] true; q.push({x, y}); } } } } } } cout -1; return 0; }