题解：P10486 电路维修

· · 题解

思路：

每条电线要么需要转向，要么不需要转向，如果不用转向就能走通，不转向的情况，肯定是比转向要好的。所以如果搜索的时候先搜不转向的，再搜转向的，那速度会快很多。（使用双端队列）如果不需要转向，那就从队首入队，这样就可以先搜到，需要转向就在队尾入队，搜完了不转向的才会搜这些，出队的话就统一从队首出去即可。判断经过的电线要走的方向是否跟原图的方向一致，如果要转向，队首入队，步数加一，要不然队尾入队，步数还是原来的不变，可以使用一个二维数组去记忆化每个格子的步数，然后就没有然后了。

代码实现


#include<bits/stdc++.h>
#define N 505
#define IOS ios::sync_with_stdio(false)
#define IN cin.tie(NULL)
#define OUT cout.tie(NULL)
using namespace std;
const int dx[4]={1,-1,-1,1};
const int dy[4]={1,1,-1,-1};
const int ix[4]={0,-1,-1,0};
const int iy[4]={0,0,-1,-1};
const char c[5]="\\/\\/";
deque<int> q,qu;
char a[N][N];//存图
int v[N][N],n,m,t;//记忆化数组
void BFS(){
    //初始化，因为要求最小，所以要设最大 
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            v[i][j]=INT_MAX;
        }
    }
    q.push_back(0);
    qu.push_back(0);
    v[0][0]=0; 
    while(!q.empty()){
        int xx=q.front();
        int yy=qu.front();
        q.pop_front();
        qu.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(c[i]!=a[inx][iny]){//需要转向 
                    int t=v[xx][yy]+1;//因为需要转向，所以步数需要加一 
                    if(t<v[dnx][dny]){
                        q.push_back(dnx);
                        qu.push_back(dny);
                        v[dnx][dny]=t;  
                    }
                }
                else{//不用转向 
                    int t=v[xx][yy];//因为不用转向，所以赋值即可 
                    if(t<v[dnx][dny]){//同上 
                        q.push_front(dnx);
                        qu.push_front(dny);
                        v[dnx][dny]=t;  
                    }
                }
            }
        }
    }
    cout<<v[n][m]<<endl;
}
int main(){
    IOS;IN;OUT; 
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m; 
        for(int i=0;i<n;i++) cin>>a[i];
        if((n+m)%2==1) cout<<"NO SOLUTION"<<endl;//判断是否能到达终点//因为沿对角线走时横纵坐标的和一定是偶数，所以只要判断一下重点横纵坐标的和是否是偶数即可。
        else BFS();
    }
    return 0;       
}