题解 P2243 【电路维修】
z3475
2018-06-20 21:56:31
由楼上所说,这电路图可以转化成图，题目任务就是求最短路。
但是有几个需要注意的地方
1. 电路图的点转成图上的点
2. 存图可以用邻接表,vector<int>[],但是注意到题目中一个电路图上的点最多只可以有四条边，int M[251002][5]也行。
3. 在进行bfs中时如果你的dis[]没有作bfs的状态，千万不要听lyd书上说的第一次访问优化的方法
附代码
```c++
#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));
}
}
```