例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语句
