洛谷P4667 Switch the Lamp On 电路维修 (Day1)

url: https://www.luogu.com.cn/problem/P4667

tag:
BalticOI 2011，最短路，双端队列，bfs

思路：
用双端队列的bfs，每次走到下一步的时候判断方向是否相同，相同且更新之后路径变小就插到队列前面，不同且更新之后路径变小就插到队列后面。判断是否无解就判断一下终点横纵坐标和是否为奇数，为奇数就无解，因为起点和终点的横纵坐标奇偶性相同（沿对角线走）。
参考： https://www.luogu.com.cn/article/d1fliiql

代码：

#include <iostream>
#include <deque>
#include <cstring>
using namespace std;
const int N = 550;
const int dx[4] = {1, -1, -1, 1};
const int dy[4] = {1, 1, -1, -1};
const char a[5] = "\\/\\/";
const int ix[4] = {0, -1, -1, 0};
const int iy[4] = {0, 0, -1, -1};
deque<int> x;
deque<int> y;
int n, m;
char d[N][N];
int vis[N][N];

void bfs()
{
    memset(vis, 0x3f, sizeof vis);
    x.push_back(0);
    y.push_back(0);
    vis[0][0] = 0;
    while (!x.empty()) {
        int xx = x.front();
        int yy = y.front();
        x.pop_front();
        y.pop_front();
        for (int i = 0; i < 4; i++) {
            int dnx = xx + dx[i];
            int dny = yy + dy[i];
            int inx = xx + ix[i];
            int iny = yy + iy[i];
            if (dnx >= 0 && dnx <= n && dny >= 0 && dny <= m) {
                if (a[i] != d[inx][iny]) {
                    int t = vis[xx][yy] + 1;
                    if (t < vis[dnx][dny]) {
                        x.push_back(dnx);
                        y.push_back(dny);
                        vis[dnx][dny] = t;
                    }
                } else {
                    int t = vis[xx][yy];
                    if (t < vis[dnx][dny]) {
                        x.push_front(dnx);
                        y.push_front(dny);
                        vis[dnx][dny] = t;
                    }
                }
            }
        }
    }
    cout << vis[n][m] << endl;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> d[i];
    if ((n + m) % 2) cout << "NO SOLUTION" << endl;
    else bfs();
    return 0;
}