z3475 的博客

题解 P2243 【电路维修】

由楼上所说,这电路图可以转化成图,题目任务就是求最短路。

但是有几个需要注意的地方

  1. 电路图的点转成图上的点

  2. 存图可以用邻接表,vector<int>[],但是注意到题目中一个电路图上的点最多只可以有四条边,int M[251002][5]也行。

  3. 在进行bfs中时如果你的dis[]没有作bfs的状态,千万不要听lyd书上说的第一次访问优化的方法

附代码

#include <bits/stdc++.h>

using namespace std;
#define pii pair<int,int>
pii M[251002][5];
int n[251002];
inline char gc(){
    register char t=getchar();
    while (t!='\\'&&t!='/') t=getchar();
    return t;
}
#define ri register int
inline void cnt(ri from,ri to,ri v){M[from][n[from]++]=pii(to,v);}
inline void cnt2(ri from,ri to,ri v){cnt(from,to,v);cnt(to,from,v);}
int dis[251002];
int R,C,to;
inline int f(ri i,ri j){return i*C+i+j;}
bool bfs(){
    deque<int> d;
    d.push_front(0);dis[0]=0;
    while (!d.empty()){
        ri from=d.front();d.pop_front();
        if (from==to) return true;
        for (ri t=0;t<n[from];t++){
            register pii &i=M[from][t];
            if (i.second==0){
                if (dis[i.first]>dis[from]){
                    dis[i.first]=dis[from];
                    d.push_front(i.first);
                }
            }else{
                if (dis[i.first]>dis[from]+1){
                    dis[i.first]=dis[from]+1;
                    d.push_back(i.first);
                }
            }
        }
    }
    return false;
}
int main(){
    ri T;
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&R,&C);
        for (ri i=1;i<=R;i++)
            for (ri j=1;j<=C;j++)
                if (gc()=='\\'){
                    cnt2(f(i,j),f(i-1,j-1),0);
                    cnt2(f(i-1,j),f(i,j-1),1);
                }else{
                    cnt2(f(i,j),f(i-1,j-1),1);
                    cnt2(f(i-1,j),f(i,j-1),0);
                }
        memset(dis,127,sizeof(dis));
        to=f(R,C);
        if (bfs()){
            cout << dis[to] << endl;
        }else{
            cout << "NO SOLUTION" << endl;
        }
        memset(n,0,sizeof(n));
    }
}

2018-06-20 21:56:31 in 题解