Acwing_175电路维修【双端队列+宽搜】
程序员文章站
2022-05-24 08:48:03
...
题目链接:Acwing_175电路维修
思路分析:
双端队列+广度优先搜索
- 首先把电路板上每一个格子点(交叉点)看作无向图中的节点,我们认为两个节点x和y是某个小方格的两个对角,那么如果说x和y的线段’’,那么我们可以认为边权为0,反之如果x和y线段是’/’,那么我们的边权视为1,说明要旋转一次才能够连上.
- 现在我们得到了一张完美的边权0或1的无向图,那么和普通广搜一样,我们唯一的改变就是,如果说当前新状态的边权为0,那么我们就放到队头先走,因为我们要满足两端性和单调性,而为了这个单调性,如果说当前新状态边权为1,那么我们就只能压入到队尾.
AC代码:
//双端队列广搜
/*
1、dx[]和dy[]表示可以去其他点的方向
2、id[]和iy[]表示需要踩某个方向的各种才能去到相应的点
3、cs[]表示当前点走到4个方向的点理想状态下格子形状(边权是0的状态)
*/
#include<iostream>
#include<cstring>
#include<deque>
#include<cstdio>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 505,M=N*N;
int n, m;
char g[N][N];
int dist[N][N];
PII q[M];
bool st[N][N];
int bfs() {
deque<PII> q;
int hh = 0, tt = 0;
q.push_back({ 0,0 });
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
char cs[5] = "\\/\\/";
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 };
q.push_back({ 0,0 });
while (q.size()) {
auto t = q.front();
q.pop_back();
int x = t.x, y = t.y;
if (x == n && y == m) return dist[x][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]);
int d = dist[x][y] + w;
if (d <= dist[a][b]) {
dist[a][b] = d;
if (!w) q.push_front({a,b});
else q.push_back({a,b});
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
if (n + m & 1) printf("NO SOLUTION");//n+m为奇数
else {
for (int i = 0; i < n; i++) scanf("%s", g[i]);
printf("%d\n", bfs());
}
}
}
上一篇: 图的遍历算法——DFS、BFS原理及实现
下一篇: proxool简介