题目描述

电路板的整体结构如下图所示。

关于 dxdy和 ixiy — 坐标点偏移和格点偏移

首先输入的斜线(电路)从图片中看是跨越了一个格子的线, 但实际存储时一条线存储在了一个坐标点上,

即第一条线存储在了g[0][0]中, 最后一条线存储在了g[n - 1][m - 1]中。但我们在宽搜时是按照坐标点来搜的:

从左上角第一条线的源点(0, 0)出发, 最后走到了右下角最后一条线的终点(n, m)

所以dx、dy是坐标点(宽搜路线)的偏移, 不同于普通的图, 本题每次只能斜着走, 并跨越一个格子, 坐标的偏移上x和y应该同时变化

ix、iy是每当按坐标点走过一步时, 所能跨越字符所在格子的位置。

当从(1,1)走到所能走到的坐标点和所经历的格点如图所示:

(蓝色为存储在g中的格点位置)、(黑色为实际搜索的坐标点)

每次扩展一步时, 利用ixiy可以求出走出这一步所跨越的电线是否是我们期望的那样 : 左上\ 右上 / 右下 \ 左下 /

如果不是(需要旋转才能连通), 则”边权”为1。 如果已经连通 则边权为0

然后根据双端队列求解边权只有0和1的带权图的解法, 分别放到队尾和队头

代码中dxdy、ixiy、连通字符cs[] 是按照左上 右上 右下 左下 来构造的。三者必须按照统一的方向构造

带注释C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;
using T = pair<int, int>;

const int N = 510, inf = 0x3f;

char g[N][N];
int st[N][N], dist[N][N];
// dxdy表示坐标点的方向,因为只能斜着走,所以每次偏移量是|2|
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
// ixiy代表每次从坐标点跨越格点所经过的字符(\或/) 的偏移
/*
进一步解释为:第一个方格的\线所代表的坐标为(0,0) 其跨越了坐标点(0,0)到(1,1)
即dxdy为坐标点偏移 ixiy为格点偏移
*/
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
int k, n, m;

int bfs()
{
    // 多组测试数据 每次都要初始化
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    //起始点要初始化为0
    dist[0][0] = 0;

    // 根据四个方向偏移 所能走到的四种电路的形状 分别为: 左上\ 右上 / 右下 \ 左下 / 这里要转义
    char cs[5] = "\\/\\/";

    deque<T> q;
    q.push_front({0, 0});

    while(q.size()){
        auto t = q.front();
        q.pop_front();

        int a = t.first, b = t.second;
        /*注意
            双端队列中存储的是坐标点的坐标,即dxdy偏移下的坐标
            所以最终会走到右下角的那个 '点' 不是格子 所以走到(n, m)时返回
        */
        if(a == n && b == m) return dist[n][m];

        if(st[a][b]) continue;
        st[a][b] = true;

        for(int i = 0; i < 4; i ++ ){
            // 坐标点偏移
            int u = a + dx[i], v = b + dy[i];
            if(u < 0 || v < 0 || u > n || v > m) continue;

            // 格点偏移 即经过坐标点偏移后所经过的格点
            int ga = a + ix[i], gb = b + iy[i];
            //检查所经过的格点是不是我们想要的、连通的那种格点
            int w = (g[ga][gb] != cs[i]);
            // 如果是 则距离算为0 如果不是,即需要旋转一下才能连通 则距离算为1
            int d = dist[a][b] + w;
            // 如果新扩展的坐标点可以被更新 就入队
            if(d < dist[u][v]){
                dist[u][v] = d;
                // 由双端队列广搜的解法 如果扩展的这条边为1 就加入队尾 如果是0就加入对头
                if(!w) q.push_front({u, v});
                else q.push_back({u, v});
            }
        }
    }
    return -1;
}

int main()
{
    cin >> k;
    while(k -- )
    {
        cin >> n >> m;
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < m; j ++ )
                cin >> g[i][j];

        // 这一步是为什么 参考yls的视频讲解
        if(n + m & 1) puts("NO SOLUTION");
        else printf("%d\n", bfs());
    }
    return 0;
}