双端队列广度优先搜索

双端队列广搜

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

题目描述

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障，导致无法启动。
电路板的整体结构是一个$R$R行$C$C列的网格（$R,C≤500$R,C≤500），如下图所示。

每个格点都是电线的接点，每个格子都包含一个电子元件。
电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后，它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。
她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。
不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。
注意：只能走斜向的线段，水平和竖直线段不能走。

输入格式

输入文件包含多组测试数据。
第一行包含一个整数$T$T，表示测试数据的数目。
对于每组测试数据，第一行包含正整数$R$R和$C$C，表示电路板的行数和列数。
之后$R$R行，每行$C$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 <iostream>
#include <cstring>
#include <deque>

#define x first
#define y second

using namespace std;

const int N = 510;

typedef pair<int, int> 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<PII> 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;
}