AcWing 175. 电路维修

原题链接

考察:双端队列bfs

思路:

        双端队列常用于距离只有0,1的情况.当距离为0时,更新的点放在队头.当距离为1时,更新的点放在队尾.

        判断01距离不用写冗长的if代码.可以参照方向数组预设距离为0的斜杠应该有的方向.

        这里当出队的距离才是确定了此点的最短距离.

 1 #include <iostream> 2 #include <cstring> 3 #include <deque> 4 using namespace std; 5 const int N = 510; 6 typedef pair<int,int> PII; 7 char mp[N][N]; 8 int n,m,T,dist[N][N]; 9 char pre[] = {"\\//\\"};10 int xx[4] = {1,1,-1,-1},yy[4] = {1,-1,1,-1};11 bool st[N][N];12 int bfs(int sx,int sy)13 {14 deque<PII> q;15  q.push_back({sx,sy});16 memset(dist,0x3f,sizeof dist);17 memset(st,0,sizeof st);18 dist[sx][sy] = 0;19 while(q.size())20  {21 PII it = q.front();//实际是模拟了dijkstra算法.距离短的放前面,这样第一次到的点就是最短的点.22 int x= it.first,y = it.second;23  q.pop_front();24 if(st[x][y]) continue;//已经用此点更新过就没必要再更新.25 st[x][y] = 1;26 for(int i=0;i<4;i++)27  {28 int dx = x+xx[i],dy = y+yy[i];29 if(dx>0&&dx<=n+1&&dy>0&&dy<=m+1)30  {31 char c = mp[min(dx,x)][min(dy,y)];32 int w = 1;33 if(c==pre[i]) w = 0;34 if(dist[dx][dy]>dist[x][y]+w)35  {36 dist[dx][dy] = dist[x][y]+w;37 if(!w) q.push_front({dx,dy});38 else q.push_back({dx,dy});39  }40  }41  }42  }43 return dist[n+1][m+1];44 }45 int main()46 {47 scanf("%d",&T);48 while(T--)49  {50 scanf("%d%d",&n,&m);51 for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);52 if(n+m&1) puts("NO SOLUTION");53 else printf("%d\n",bfs(1,1));54  }55 return 0;56 }

 

相关文章