AcWing 175. 电路维修（双端队列广搜）

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
const int N=510;
int t,r,c;
int dist[N][N],st[N][N];
char g[N][N];
int bfs(){
    deque<pii>q;
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[0][0]=0;
    char tep[10]="\\//\\";
    int dx[]={-1,-1,1,1},dy[]={-1,1,-1,1};
    int idx[]={-1,-1,0,0},idy[]={-1,0,-1,0};
    q.push_back({0,0});
    while(q.size()){
        pii now=q.front();
        q.pop_front();
        int x=now.x,y=now.y;
        //cout<<x<<" "<<y<<endl;
        if(st[x][y])continue;
        st[x][y]=1;
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<0||nx>r||ny<0||ny>c)continue;
            int testx=x+idx[i],testy=y+idy[i];
            int t=dist[x][y]+(g[testx][testy]!=tep[i]);
            if(t<dist[nx][ny]){
                dist[nx][ny]=t;
                if(g[testx][testy]!=tep[i]){
                    q.push_back({nx,ny});
                }
                else q.push_front({nx,ny});
            }
        }
    }
    return dist[r][c];
}
int main(){
    cin>>t;
    while(t--){
        cin>>r>>c;
        for(int i=0;i<r;i++){
            cin>>g[i];
        }
        int t=bfs();
        if(t==0x3f3f3f3f)puts("NO SOLUTION");
        else cout<<t<<endl;
    }
}