https://www.acwing.com/problem/content/177/

双端队列BFS

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 600;
using PPI = pair<int, int>;
char tb[N][N]; //储存电线初始状态
int dis[N][N];  //储存起点到各点的距离
bool vis[N][N]; 
int m, n;

void bfs()
{


    deque<PPI> q;
    int mx[4] = {
   1, -1, -1, 1}; int my[4] = {
   1, -1, 1, -1}; //四个移动方向, 右下 左上 右上 左下
    int cx[4] = {
   0, -1, -1, 0}; int cy[4] = {
   0, -1, 0, -1};
    char wire[] = "\\\\//";     //电线的四种状态
    memset(vis, false, sizeof vis);
    memset(dis, 0x3f, sizeof dis);
    dis[0][0] = 0;
    q.push_back({
   0, 0});

    while (!q.empty()) {

        auto f = q.front();
        q.pop_front();
        if (vis[f.x][f.y])
            continue;
        vis[f.x][f.y] = true;
        //出队时才能再设为不可访问
        if (f.x == m and f.y == n) {

            cout << dis[m][n] << endl;
            return;
        }
        for (int i = 0; i < 4; i++) {

            int nx = f.x + mx[i], ny = f.y + my[i];
            int use_x = f.x + cx[i], use_y = f.y + cy[i]; //现在在使用哪个格子的电线
            if (nx >= 0 and nx < m + 1 and ny >= 0 and ny < n + 1) {

                int w = (tb[use_x][use_y] != wire[i]);    //若不需要转动电线则边权为0， 否则边权为1
                if (dis[nx][ny] <= dis[f.x][f.y] + w)
                    continue;
                if (w) {

                    //边权为1则尾插
                    dis[nx][ny] = dis[f.x][f.y] + w;
                    q.push_back({
   nx, ny});
                }
                else {

                    //头插
                    dis[nx][ny] = dis[f.x][f.y];
                    q.push_front({
   nx, ny});
                }
            }
        }
    }
    printf("NO SOLUTION\n");
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--) {

        cin >> m >> n;
        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                cin >> tb[i][j];
            }
        }
        if ((m + n) & 1) {

            //x y 和为奇数的点无法到达
            printf("NO SOLUTION\n");
        }
        else
            bfs();
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}