本文主要是介绍算法提高之电路维修,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
算法提高之电路维修
-
核心思想:双端队列bfs
-
dijkstra算法的拓展情况:边权(旋转次数)只有0和1
-
dijkstra算法要求:每次取离原点最近的点 去更新其他相邻点距离(多次)
-
如何实现:将所有边权为0的边连的点放入队头,边权为1的放入队尾
-
此时队头一定是距离原点最近的点(之一)
-
-
-
#include <iostream>#include <cstring>#include <algorithm>#include <deque>#define x first#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 510,M = N*N;int dist[N][N];int n,m;char g[N][N]; //存图bool st[N][N];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}; //四个格方向int bfs(){deque<PII> q;q.push_back({0,0});memset(st, 0, sizeof st); //多组数据 清空memset(dist,0x3f,sizeof dist);dist[0][0] = 0;while(q.size()){PII t = q.front();q.pop_front();int x = t.x,y = t.y;if(st[x][y]) continue; //取出的点一定是已经确定距离最近的点 用一次即可st[x][y] = true;for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i]; //四方向 求点坐标if (a < 0 || a > n || b < 0 || b > m) continue;int ga = x+ix[i],gb = y+iy[i]; //格子坐标int w = (g[ga][gb] != cs[i]); //边权:当前图案和合法图案不一致 为需要旋转的1int d = dist[x][y] + w; //新的距离if(d < dist[a][b]){dist[a][b] = d;if(w) q.push_back({a,b}); //边权为1 加到队尾else q.push_front({a,b});}}}return dist[n][m]; //点(n,m)到原点距离}int main(){int T;cin>>T;while(T--){cin>>n>>m;for(int i=0;i<n;i++) cin>>g[i];int t = bfs();if(t == 0x3f3f3f3f) puts("NO SOLUTION");else cout<<t<<endl;}}
这篇关于算法提高之电路维修的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!