题解 P2243 【电路维修】

明显的一个搜索。 将每个方格的四个点都提出来， 若该方格的电线为‘\’，则给左上的点和右下的点连一条边权为$0$的边，给右上的点和左下的点连一条边权为$1$的边； 若为‘/’，则给左上的点和右下的点连一条边权为$1$的边，给右上的点和左下的点连一条边权为$0$的边。 即如下图所示(图画的不好见谅)。  思路很明确，这不就是个最短路吗，不过很抱歉这题把普通的$SPFA$给卡掉了。 所以这题应用堆优化$DJ$或是$SPFA+SLF+LLL$优化。 但是，这题实际上是可以用**双端广搜**解决的，而且理论上应该比上述两方法还要快！ 因为这题边权只有$0$和$1$两种情况，所以可以用双端广搜。 实现方法就是在广搜过程中找到了一条边， **若边权为$1$，则和正常广搜一样从队尾入队；若边权为$0$，则从队首入队。** 即在广搜过程中保持队列单调性，使其每次都能优先遍历边权为$0$的边。 不过我可能敲了个奇葩的算法，貌似是双端$SPFA$？？ 感觉跑的速度比原汁原味的双端广搜要慢，但又比最短路算法快？？ 不管怎样还是先上代码吧。 ```cpp #include<cstdio> #include<cstring> using namespace std; const int N=3e5+10; const int M=3e6+10; int fi[N],di[M],da[M],ne[M],dis[N],nxt[M],nmb[M],n,m,l; bool v[N]; //fi,di,da,ne为存边数值,dis记录距离,v记录点有无经过 //nxt,nmb则为数组模拟链表 //nxt记录下一个空间(即后驱)，nmb则为这个空间对应的数据 //因为要实现从队首入队的话自然使用链表是不错的 //而我嫌STL常数过大，所以是用数组来模拟链表 inline int re()//快读 { int x=0; char c=getchar(); for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar()) x=x*10+(c-'0'); return x; } inline int re_l()//读取方格数据并判断是'/'还是'\'的函数 { char c=getchar(); for(;c!='\\'&&c!='/';c=getchar()); return c=='/'?1:0; } inline void add(int x,int y,int z)//加边 { di[++l]=y; da[l]=z; ne[l]=fi[x]; fi[x]=l; di[++l]=x; da[l]=z; ne[l]=fi[y]; fi[y]=l; } inline int ch(int x,int y)//给每个点一个标签 { return (x-1)*(m+1)+y; } int main() { int i,j,x,y,t,head,tail,s,ed; bool p=1; t=re(); while(t--)//多组数据 { n=re(); m=re(); head=l=0;//初始化&清空数组 s=tail=1; p=1; ed=ch(n+1,m+1); memset(fi,0,sizeof(fi)); memset(v,0,sizeof(v)); memset(dis,50,sizeof(dis)); memset(nxt,0,sizeof(nxt)); memset(nmb,0,sizeof(nmb)); for(i=1;i<=n;i++) for(j=1;j<=m;j++)//输入方格数据 { if(re_l())//加边方法即为前面所述 { add(ch(i,j),ch(i+1,j+1),1); add(ch(i+1,j),ch(i,j+1),0); } else { add(ch(i,j),ch(i+1,j+1),0); add(ch(i+1,j),ch(i,j+1),1); } } dis[1]=0;//初始化 v[1]=1; nxt[0]=1; nmb[1]=1; while(p)//p用来记录有无到达终点，有则直接退出 { head=nxt[head];//每次通过后驱到下一个空间 if(!head)//若没有后驱了就表明搜索完毕 break; x=nmb[head];//取出该空间对应的数 for(i=fi[x];i&&p;i=ne[i])//枚举边 { y=di[i]; if(!v[y]||dis[y]>dis[x]+da[i])//如果没有遍历过或是之前遍历的并不是最短的 { s++;//给链表申请一个新空间 if(da[i])//判断边权 {//若为1则从队尾入队 nxt[tail]=s;//在链表末端空间打上后驱 tail=s;//更新末端 } else//若为0则从队首入队 { nxt[s]=nxt[head]; //将目前遍历的空间的后驱过继给新增空间 //即将原本队列置于新增空间后面 nxt[head]=s; //将目前遍历的空间的后驱改为新增空间 //这样下一次循环就能先遍历新增空间了 //于是就实现了将新增空间置于队首的功能 if(!nxt[s]) tail=s; //一个小细节 //若目前队列为空，即队首就是队尾的情况 //也要更新末端 } nmb[s]=y;//给新增空间附上数值 v[y]=1;//记录该点 dis[y]=dis[x]+da[i];//修改距离 if(y==ed)//若到达终点，直接退出搜索 p=0; } } } if(p)//若没有到达终点说明无解 printf("NO SOLUTION\n"); else printf("%d\n",dis[ed]); } return 0; } ``` 该奇葩算法跑了$460ms$，而我的朴素$SPFA$在开$O^2$的情况下跑了$2784ms$，且最后一个点为$932ms$，勉强卡了过去，可见该奇葩算法的效率还是挺高的。 下面上下巨佬$lyd$的标准双端广搜，跑了$204ms$。 ```cpp #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int cap = 500010; int dist[510][510]; char map[510][510]; bool proc[510][510]; pair<int, int> queue[cap * 2]; int r, c, li, ri; inline bool valid (int x, int y) { return x >= 0 && x <= r && y >= 0 && y <= c; } inline void que_add (int x, int y, int v) { if (dist[x][y] < 0 || v < dist[x][y]) { dist[x][y] = v; if (li == ri || v > dist[queue[li].first][queue[li].second]) queue[ri++] = make_pair(x, y); else queue[--li] = make_pair(x, y); } } int main () { int kase; for (scanf("%d", &kase); kase; --kase) { scanf("%d %d", &r, &c); if ((r + c) % 2) { for (int i = 0; i < r; i++) scanf("%s", map[i]); printf("NO SOLUTION\n"); } else { for (int i = 0; i < r; i++) scanf("%s", map[i]); li = ri = cap; queue[ri++] = make_pair(0, 0); memset(dist, -1, sizeof dist), dist[0][0] = 0; memset(proc, false, sizeof proc); while (li != ri) { int cx = queue[li].first, cy = queue[li].second; ++li; if (valid(cx - 1, cy - 1)) { if (map[cx - 1][cy - 1] == '\\') que_add(cx - 1, cy - 1, dist[cx][cy]); else que_add(cx - 1, cy - 1, dist[cx][cy] + 1); } if (valid(cx - 1, cy + 1)) { if (map[cx - 1][cy] == '/') que_add(cx - 1, cy + 1, dist[cx][cy]); else que_add(cx - 1, cy + 1, dist[cx][cy] + 1); } if (valid(cx + 1, cy - 1)) { if (map[cx][cy - 1] == '/') que_add(cx + 1, cy - 1, dist[cx][cy]); else que_add(cx + 1, cy - 1, dist[cx][cy] + 1); } if (valid(cx + 1, cy + 1)) { if (map[cx][cy] == '\\') que_add(cx + 1, cy + 1, dist[cx][cy]); else que_add(cx + 1, cy + 1, dist[cx][cy] + 1); } } printf("%d\n", dist[r][c]); } } return 0; } //因为是从lyd巨佬所著书的光盘里复制的，所以侵删 ```