欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

双端队列广度优先搜索

程序员文章站 2022-06-12 15:24:55
...

双端队列广搜

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

题目描述

达达是来自异世界的魔女,她在漫无目的地四处漂流的时候,遇到了善良的少女翰翰,从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障,导致无法启动。
电路板的整体结构是一个RRCC列的网格(R,C500R,C≤500),如下图所示。
双端队列广度优先搜索
每个格点都是电线的接点,每个格子都包含一个电子元件。
电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后,它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源,右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变,电路板可能处于断路的状态。
她准备通过计算,旋转最少数量的元件,使电源与发动装置通过若干条短缆相连。
不过,电路的规模实在是太大了,达达并不擅长编程,希望你能够帮她解决这个问题。
注意:只能走斜向的线段,水平和竖直线段不能走。

输入格式

输入文件包含多组测试数据。
第一行包含一个整数TT,表示测试数据的数目。
对于每组测试数据,第一行包含正整数RRCC,表示电路板的行数和列数。
之后RR行,每行CC个字符,字符是/\中的一个,表示标准件的方向。

输出格式

对于每组测试数据,在单独的一行输出一个正整数,表示所需的缩小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通,输出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次对应的电子元件。

在一个边权只有01的无向图中搜索最短路径可以使用双端队列进行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;
}