电路维修
本题的特点是可以看成边权为0或1的最短路问题,这种问题一般可以使用双端队列来解决,如果遍历到边权为0需要更新的点时,把该点放在双端队列的最前端,如果是边权为1的点就放在双端队列的最后面。
下面解释一下各个数组的作用:
- st数组表示该点是否被遍历过
- dist数组表示该点当前的最短距离
- g数组存储每一个经过的路线是什么方向的
- dx和dy数组表示从当前点可以走到的点的方向对应的下标
- ix和iy数组表示从当前点走到的点的路径对应在路径数组g的下标
还有一些需要注意的点:
- 本题由于边权不是全为1,所以在入队的时候的dist不是最短路径,可能还会被更新一遍
- 通过看图发现,本题有一些点是无法走到的,也就是不在连接原点的路径上的点,所以我们才能把本题看成边权为1和0的图的最短路问题
#include<iostream>
#include<cstring>
#include<algorithm>
#include<deque>
#define x first
#define y second
using namespace std;
const int N = 510,M=N*N;
typedef pair<int,int> pii;
bool st[N][N];
int dist[N][N];
char g[N][N];
int n,m,T;
int bfs(){
memset(st,0,sizeof st);
memset(dist,0x3f,sizeof dist);
dist[0][0]=0;
deque<pii> q;
q.push_back({0,0});
char cs[]="\\/\\/";
int dx[4]={-1,-1,1,1},dy[4]={-1,1,1,-1};
int ix[4]={-1,-1,0,0},iy[4]={-1,0,0,-1};
while(q.size()){
pii t=q.front();
q.pop_front();
if(st[t.x][t.y]==true)continue;
st[t.x][t.y]=true;
for(int i=0;i<4;i++){
int a=t.x+dx[i],b=t.y+dy[i];
if(a<0||a>n||b<0||b>m)continue;
int ca=t.x+ix[i],cb=t.y+iy[i];
int d=dist[t.x][t.y]+(cs[i]!=g[ca][cb]);
if(d<dist[a][b]){
dist[a][b]=d;
if(g[ca][cb]!=cs[i])q.push_back({a,b});
else q.push_front({a,b});
}
}
}
return dist[n][m];
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%s",g[i]);
int t = bfs();
if(t==0x3f3f3f3f)puts("NO SOLUTION");
else printf("%d\n",t);
}
return 0;
}