Luogu_P2243 电路维修【题解】 双端队列bfs
题面：https://www.luogu.org/problem/P2243
建边。
对角线有相连路的边权为0，没有的为1。
然后双端队列bfs求最短路。
将边权为0的到的点从队头入队。
边权为1到的点从队尾入队。
这样可以保证最优。
代码如下：
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=510; int T,r,c,dis[maxn][maxn],vis[maxn][maxn]; char s[maxn][maxn]; vector<pair<pair<int,int>, int> > p[maxn][maxn]; deque<pair<int,int> > q; inline void add(int xx,int yy,int x,int y,int z){ p[xx][yy].push_back(make_pair(make_pair(x,y), z)); } inline void work(){ scanf("%d%d",&r,&c); for(int i=1;i<=r;i++) scanf("%s",s[i]+1); for(int i=0;i<=r;i++) for(int j=0;j<=c;j++) p[i][j].clear(); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(s[i][j]=='/'){ add(i-1,j-1,i,j,1); add(i,j,i-1,j-1,1); add(i,j-1,i-1,j,0); add(i-1,j,i,j-1,0); }else{ add(i-1,j-1,i,j,0); add(i,j,i-1,j-1,0); add(i,j-1,i-1,j,1); add(i-1,j,i,j-1,1); } memset(dis,0x3f,sizeof(dis)); dis[0][0]=0; memset(vis,0,sizeof(vis)); q.clear(); q.push_back(make_pair(0,0)); while(q.size()){ int x=q.front().first,y=q.front().second; q.pop_front(); vis[x][y]=1; if(x==r&&y==c){ printf("%d ",dis[r][c]); return; } for(int i=0;i<p[x][y].size();i++){ int xx=p[x][y][i].first.first; int yy=p[x][y][i].first.second; int z=p[x][y][i].second; if(vis[xx][yy]) continue; if(dis[xx][yy]>dis[x][y]+z){ dis[xx][yy]=dis[x][y]+z; if(z) q.push_back(make_pair(xx,yy)); else q.push_front(make_pair(xx,yy)); } } } printf("NO SOLUTION "); return; } signed main() { scanf("%d",&T); while(T--) work(); system("pause"); return 0; }