本文共 3112 字，大约阅读时间需要 10 分钟。

双端队列广搜

在一个边权只有0、1的无向图中搜索最短路径可以使用双端队列进行BFS。其原理是当前可以扩展到的点的权重为0时，将其加入队首；权重为1时，将其加入队尾。

题目描述

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。

翰翰的家里有一辆飞行车。 有一天飞行车的电路板突然出现了故障，导致无法启动。 电路板的整体结构是一个$R$行$C$列的网格（$R,C\le 500$），如下图所示。 每个格点都是电线的接点，每个格子都包含一个电子元件。 电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。 在旋转之后，它就可以连接另一条对角线的两个接点。 电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。 达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。 她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。 不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。 注意：只能走斜向的线段，水平和竖直线段不能走。

输入格式

输入文件包含多组测试数据。

第一行包含一个整数$T$，表示测试数据的数目。 对于每组测试数据，第一行包含正整数$R$和$C$，表示电路板的行数和列数。 之后$R$行，每行$C$个字符，字符是/和\中的一个，表示标准件的方向。

输出格式

对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。

如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。

算法思想

把一个网格视为一个电子元件，在遍历的过程中只能走斜向的线段，水平和竖直方向不能走。因此

1、从(0,0)点出发不能到达那些 x+y是奇数的点。所以如果(m + n) & 1 == 1时，此题无解。

2、从任意一点(x,y)出发能够扩展到4个方向（从左上角开始顺时针方向，以下皆同）的点有(x−1,y−1)、(x−1,y+1)、(x+1,y+1)、(x+1,y−1)

3、对于任意一点(x,y)，对应4个方向的电子元（以左上角为顶点）在数组中的下标为(x−1,y−1)、(x−1,y)、(x,y)、(x,y−1)，如下图所示：

4、对于任意一点(x,y)，对应4个方向上表示通路对应的字符分别是 \、/、\、/。

5、从任意一点(x,y)出发能够扩展到的点可以分为两类：一类是权值为0的点，即已经是通路、不需要旋转对应的电子元件；另一类是权值为1的点，即需要旋转1次对应的电子元件。

在一个边权只有0、1的无向图中搜索最短路径可以使用双端队列进行BFS。其原理是当前可以扩展到的点的权重为0时，将其加入队首；权重为1时，将其加入队尾。

代码实现

#include 
   
    #include 
    
     #include 
     
      #define x first#define y secondusing namespace std;const int N = 510;typedef pair
      
        PII;char g[N][N];int n, m;//可以扩展到的4个方向的坐标差值int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};//可以扩展到的4个方向对应的电子元件在g[][]中的下标差值int ix[] = {-1, -1, 0, 0}, iy[] = {-1, 0, 0, -1};//dis[i][j]表示(0,0)点到(i,j)点距离//st[i][j]表示(i,j)已经扩展过int dis[N][N], st[N][N];//cs[]表示对应4个方向表示通路的字符，注意'\'需要转义字符char cs[] = "\\/\\/";int bfs(){    memset(st, 0, sizeof st);    memset(dis, 0x3f, sizeof dis);    dis[0][0] = 0; //从(0,0)点出发，距离为0        deque
       
         q; //双端队列    q.push_back({0, 0}); //(0, 0)点入队        while(q.size())    {        PII t = q.front(); //取出队首        q.pop_front(); //从队首出队                int x = t.x, y = t.y;                //注意：这里有 n * m 个网格，所以点的坐标应为(0,0) ~ (n, m)        if(x == n && y == m) break;                if(st[x][y]) continue;        st[x][y] = 1; //(x,y)标识为已扩展过                for(int i = 0; i < 4; i ++)        {            int a = x + dx[i], b = y + dy[i];            if(a < 0 || a > n || b < 0 || b > m) continue; //数组越界                        //(ga, gb)表示(x, y)点对应的字符在数组g[][]中的下标            int ga = x + ix[i], gb = y + iy[i];                        //g[ga][gb]表示输入的字符，cs[i]表示连通时的字符            //不相等即不连通时权重为1，相等即已连通时权重为0            int w = (cs[i] != g[ga][gb]);                         //计算距离            int d = dis[x][y] + w;                        if(d < dis[a][b]) //是否可以松弛            {                dis[a][b] = d;                //边权为0时，进入队首                if(!w) q.push_front({a, b});                //边权为1时，进入队尾                else q.push_back({a, b});            }        }    }        return dis[n][m];}int main(){    int T;    cin >> T;    while(T --)    {        cin >> n >> m;            for(int i = 0; i < n; i++) scanf("%s", g[i]);                if(n + m & 1) puts("NO SOLUTION");        else printf("%d\n", bfs());    }        return 0;}