[Wrong title] Circuit maintenance

题目链接

WA代码

#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
typedef pair<int,int> pii;
const int N = 510;
string G[N];
int r,c;
int D[N][N];
const int d1[] = {
    -1,-1,1, 1}; // 点
const int d2[] = {
    -1, 1,1,-1};
const int k1[] = {
    -1,-1,0, 0}; // 边
const int k2[] = {
    -1, 0,0,-1};
const char kk[] = "\\/\\/";
int bfs(){
    
    deque<pii> q;
    memset(D,-1,sizeof D);
    q.push_back({
    0,0});
    D[0][0] = 0;
    while(!q.empty()){
    
        int x = q.front().xx,y = q.front().yy;
        q.pop_front();
        if(x == r and y == c) break;
        for(int i = 0;i < 4;i++){
    
            int dx = x + d1[i],dy = y + d2[i];
            int kx = x + k1[i],ky = y + k2[i];
            if(dx < 0 or dy < 0 or dx > r or dy > c) continue;
            if(~D[dx][dy]) continue;
            if(G[kx][ky] == kk[i]){
    
                D[dx][dy] = D[x][y];
                q.push_front({
    dx,dy});
            } 
            else{
    
                D[dx][dy] = D[x][y] + 1;
                q.push_back({
    dx,dy});
            }
        }
    }
    return D[r][c];
}

int main(){
    
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while(t--){
    
        cin >> r >> c;
        for(int i = 0;i < r;i++) cin >> G[i];
        cout << bfs() << endl;
    }
    return 0;
}

AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<deque>
#define xx first
#define yy second
using namespace std;
typedef pair<int,int> pii;
const int N = 510;
string G[N];
int r,c;
int D[N][N];
const int d1[] = {
    -1,-1,1, 1}; // 点
const int d2[] = {
    -1, 1,1,-1};
const int k1[] = {
    -1,-1,0, 0}; // 边
const int k2[] = {
    -1, 0,0,-1};
const char kk[] = "\\/\\/";
bool st[N][N]; 
int bfs(){
    
    if((r + c) % 2) return -1;
    deque<pii> q;
    memset(D,0x3f,sizeof D);
    memset(st,false,sizeof st);
    q.push_back({
    0,0});
    D[0][0] = 0;
    st[0][0] = true;
    while(!q.empty()){
    
        int x = q.front().xx,y = q.front().yy;
        q.pop_front();
        st[x][y] = true;
        if(x == r and y == c) break;
        for(int i = 0;i < 4;i++){
    
            int dx = x + d1[i],dy = y + d2[i];
            int kx = x + k1[i],ky = y + k2[i];
            if(dx < 0 or dy < 0 or dx > r or dy > c) continue;
            if(st[dx][dy]) continue;
            if(G[kx][ky] == kk[i] and D[dx][dy] > D[x][y]){
    
                D[dx][dy] = D[x][y];
                q.push_front({
    dx,dy});
            } 
            else if(G[kx][ky] != kk[i] and D[dx][dy] > D[x][y] + 1){
    
                D[dx][dy] = D[x][y] + 1;
                q.push_back({
    dx,dy});
            }
        }
    }
    return D[r][c];
}

int main(){
    
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while(t--){
    
        cin >> r >> c;
        for(int i = 0;i < r;i++) cin >> G[i];
        int res = bfs();
        if(~res) cout << res << endl;
        else cout << "NO SOLUTION" << endl;
    }
    return 0;
}

错误原因

错误原因是,Mistakenly believe that the distance when a point is updated for the first time must be the shortest distance.

这是一个假命题.

Because one point is taken from the queue at a time$(x,y)$时,will update its four adjacent points"距离".
当$D[dx][dy]=D[x][y]+1$时,Still can not rule out being able to be from another distance$D[tx][ty]=D[x][y]$的点$(tx,ty)$,以$0$的代价从$(tx,ty)$走到$(dx,dy)$.

双端队列广搜,实际可以理解为dijkstra的简化版本.
Every time we update the distance,That is, a relaxation operation.
所以,we can imitate,Set the initial distance to （理论上的）无穷大,Then make the final obtained distance as the minimum distance in the update.
因此,这里不能使用DThe array is used as the basis for judging whether the distance of the node needs to be updated,We need to add a new state array$st$.