例 1 蓝桥杯 —— 穿越雷区展开目录
题目大意是在一个 nxn 的方阵地图上，每一个方格都标记 + 号或者 - 号，要从 A 点到 B 点。题目要求移动路线要 +- 交替，问怎么移动从 A 到 B 才是最短路径？
同样的，这道题也是一道 2D 网格图上的最短路径问题。我们仍然采用相同的思路来解决它。相较于上一讲的问题，本题主要有以下两个个不同之处：
- 起始点不在固定，而是通过字符地图给出。在这道题目中起点为 A，终点为 B
- 在移动的过程中，需要满足正负能量交错，即只能从 + 格子移动到 - 格子或从 - 格子移动到 + 格子
第一个限制条件在读入数据时，顺便将 A,B 两点的坐标进行记录即可。该题目的主要问题在第二个限制条件，在移动过程中需要满足正负能量交错。BFS 扩展节点的过程实际上就是在模拟移动的过程，换句话说，需要在扩展的过程中满足当前节点与扩展节点的属性相反。我们可以通过在 if 语句中添加条件来实现，这里给出实现代码：
- #include <iostream>
- #include <string>
- using namespace std;
- int n,x_A,y_A,x_B,y_B;
- char map[100][100];
- const int dr[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
- int head = 0,tail = 0;
- int que[10000][2],steps[100][100];
- bool inq[100][100] = {false};
- bool inMap(int x,int y)
- {
- return x >= 0 && x < n && y >= 0 && y < n;
- }
- void bfs()
- {
- que[tail][0] = x_A;
- que[tail][1] = y_A;
- tail++;
- steps[x_A][y_A] = 0;
- inq[x_A][y_A] = true;
- while(head < tail)
- {
- int x = que[head][0];
- int y = que[head][1];
- head++;
- for(int d = 0;d < 4;++d)
- {
- int nx = x + dr[d][0];
- int ny = y + dr[d][1];
- if(inMap(nx,ny) && !inq[nx][ny] &&
- map[x][y] != map[nx][ny])
- {
- steps[nx][ny] = steps[x][y] + 1;
- inq[nx][ny] = true;
- que[tail][0] = nx;
- que[tail][1] = ny;
- tail++;
- }
- }
-
- }
- }
- int main()
- {
- cin >> n;
- for(int i = 0;i < n;i++)
- {
- for(int j = 0;j < n;j++)
- {
- cin >> map[i][j];
- if(map[i][j] == 'A')
- {
- x_A = i;
- y_A = j;
- }
- if(map[i][j] == 'B')
- {
- x_B = i;
- y_B = j;
- }
- }
- }
- bfs();
- if(!inq[x_B][y_B])
- cout << -1 << endl;
- else
- cout << steps[x_B][y_B] << endl;
- return 0;
- }
首先看一下定义的变量，(x_A, y_A) 是起点坐标，(x_B, y_B) 是终点坐标。que [] 数组是 BFS 队列，head 和 tail 是头尾指针。二维数组 steps [][] 记录了到每一个位置的最短路径长度。二维数组 inq [][] 记录了每个位置是不是已经在队列里了。第 10~13 行 InMap 函数是判断坐标 (x, y) 是不是在地图上。然后我们先来看一下第 43~69 行的主函数。主函数的逻辑非常简单，首先读入地图，找出起点和终点；然后 BFS；BFS 结束后如果 (x_B, y_B) 没进过队列，说明到达不了，输出 - 1；否则直接输出 stepsx_B
第 13~33 行是 BFS 宽搜的过程。基本框架已经说明过了。具体可以看一下第 31 行，在扩展时，比较 mapx 和 map_x 的字符是否不同来决定能否移动过去
在宽搜中用 inq [][] 保证每个位置最多进队列出队列一次，而每次处理队首元素的复杂度是 O (1) 的，所以程序整体的复杂度是 $O (n^2)$
例 2 题目链接：hihoCoder1092展开目录
这道题目的大意是给定一幅字符表示的地图，大小为 n*m。地图中包含有 1 个起点 'H'，若干个座位 'S'，墙壁 '#' 和行人 'P'。其中墙壁 '#' 和行人 'P' 是不可通过的区域。座位 'S' 只可到达，不可通过
假设在地图中，只能沿着上下左右移动，且每移动一个单元格为 1 步。两个人从起点 'H' 出发，是否能够到达两个相邻的座位 'S'，且需要移动的总步数最少是多少。通过题意，我们可以发现本题主要有以下两个限制条件：
- 在该题目中，目标是从 H 字符出发，最后到达 S 字符。因此在本问题中移动不再是从左上角到右下角，而是通过字符画的形式给出起点和终点。
同时由于地图中可能出现多个不同位置的 S，也就存在了多个不同的终点。 - 在该题目中，目标不仅仅是寻找一条从起点到终点的路径。而是需要找到两个相邻的终点，并且使得从 H 到这两个点的最短路径之和最小
对于本题来说，解决的思路分为两步：
- 查询所有可以到达的终点 S。
- 枚举相邻的 S，并从中找出距离和最小的答案
第一步的解决过程显然就是最基础的 2D 网格地图最短路径问题，我们可以直接利用宽度优先搜索进行求解。将 H 点所在的位置作为初始搜索节点进行扩展，记录到达每一个 S 的最短步数。在搜索过程中我们可能会遇到一些 S 节点无法到达的情况，比如：
对于这样的 S 节点我们需要进行标记，将其设置为不可到达状态。一个简单的处理办法是将不可达位置的最短路径长度设置成一个负数，比如 - 1；或者也可以设置为一个足够大的数，比如 99999999。这里我们推荐使用 99999999 的方式，这样可以简化我们第二部分的代码
这道题完整的代码如下：
- #include <iostream>
- #include <cstdio>
- using namespace std;
- const int dr[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
- const int INF = 999999;
- int N,M,sX,sY;
- char map[102][102];
- int steps[102][102],que[10002][2];
- int head = 0,tail = 0;
- bool isValid(int x,int y)
- {
- return x >= 1 && x <= N && y >= 1 && y <= M &&
- (map[x][y] == '.' || map[x][y] == 'S');
- }
- void bfs(int startX,int startY)
- {
- steps[startX][startY] = 0;//将起点标为走过
- //起点入队
- que[tail][0] = startX;
- que[tail][1] = startY;
-
- tail++;
- while(head < tail)
- {
- int x = que[head][0];//当前队首元素的横坐标
- int y = que[head][1];//当前队首元素的纵坐标
- for(int d = 0;d < 4;++d)//枚举四个方向
- {
- int nx = x + dr[d][0];//新的横坐标
- int ny = y + dr[d][1];//新的纵坐标
- if(isValid(nx,ny) && steps[nx][ny] == INF)//isValid判断是否能走
- //steps判断是否走过，没走过值就是INF
- {
- steps[nx][ny] = steps[x][y] + 1;
- if(map[nx][ny] != 'S')//如果新的坐标位置不是S
- {
- que[tail][0] = nx;//横坐标入队
- que[tail][1] = ny;//纵坐标入队
- tail++;//队尾指针加1
- }
- }
- }
- ++head;//枚举完四个方向，队首元素出队
- }
- }
- int main()
- {
- cin >> N >> M;
- sX = sY = 0;
- for(int i = 1;i <= N;i++)
- {
- scanf("%s",map[i] + 1);
- for(int j = 1;j <= M;j++)
- {
- steps[i][j] = INF;
- if(map[i][j] == 'H')//找到起始点
- {
- sX = i;//保存起点横坐标
- sY = j;//保存起点纵坐标
- }
- }
- }
- bfs(sX,sY);//从起点开始bfs
- int ans = INF;
- for(int i = 1;i <= N;++i)
- {
- for(int j = 1;j <= M;++j)
- {
- if(map[i][j] == 'S')
- {
- if(map[i - 1][j] == 'S' &&
- ans > steps[i][j] + steps[i - 1][j])
- ans = steps[i][j] + steps[i - 1][j];
- if(map[i][j - 1] == 'S' &&
- ans > steps[i][j] + steps[i][j - 1])
- ans = steps[i][j] + steps[i][j - 1];
- /*if(map[i + 1][j] == 'S' &&
- ans > steps[i][j] + steps[i + 1][j])
- ans = steps[i][j] + steps[i + 1][j];
- if(map[i][j + 1] == 'S' &&
- ans > steps[i][j] + steps[i][j + 1])
- ans = steps[i][j] + steps[i][j + 1];*/
- }
- }
- }
- if(ans == INF)
- cout << "Hi and Ho will not have lunch." << endl;
- else
- cout << ans << endl;
- return 0;
- }
首先我们看第 46-92 行的 main 函数。第 50~62 行是在读入地图，并且找出起点 H 的坐标，同时把每个位置的最短路径距离设置成 INF，也就是之前提到的很大的数 999999
然后就是第 63 行 BFS，我们知道 BFS 执行过程中会遍历能从起点到达的所有位置，并且求出来到达这些位置的最短路径长度，保存在 steps [][] 里
第 65-85 行是找到所有相邻的一对 S 节点，求出这一对节点的最短路径之和。如果比当前最优的解 ans 更少，就更新 ans。有一个小的细节是 S 字符之间的相邻方向是相对的，如果 (x1,y1) 在 (x2,y2) 上方，那么也同样有 (x2,y2) 在 (x1,y1) 下方。因此我们只需要判定 2 个方向即可，比如下方和右方
注意我们之前给 steps [][] 赋值的初始值是 INF=999999。所以不可达的 S 字符的 steps 值将是 999999。这样若 (x1,y1) 或 (x2,y2) 中有一个不可到达时，最短路之和结果一定会大于 999999，就一定会大于 ans，自然就被排除了。若设置为 - 1 的话，则需要通过 if 语句手动判定一次
在这里也有一个小陷阱，这个足够大的数 INF 不能够设置为 INT_MAX，否则两个 INT_MAX 相加会有溢出的风险
第 10~14 的 isValid () 函数用来判断能不能访问 (x, y) 这个位置。能访问的条件除了 (x, y) 在地图范围内，还需要满足 (x, y) 只能是空地或者座位
最后是第 42~60 行的 BFS。这个 BFS 和之前几道题目的 BFS 函数基本一致。稍微有一点区别的就是我们用 stepsnX 是不是等于 INF 来判断 (nX, nY) 是不是访问过了。另外一点区别就是根据题目要求，我们只在当前节点是空地的时候才能扩展当前节点的邻居节点，如果是座位则不会扩展；具体可以看第 35 行的 if 语句
