电路维修
首先,因为只能走斜边,并且起点为 (0, 0),起点横纵坐标之和是偶数,每次走到下一个点的时候,横纵坐标之和的变化也都是 2 ,因此起点固定左上角的情况下,横纵坐标为奇数的点是走不到的,即如果右下角的横纵坐标之和为奇数是无法到达的。将操作 0 次 和操作 1 次看成边的权重分别为 0 和 1,那么问题就转化为 BFS 求最短距离了。这里采用双端队列广搜,是因为要保持 BFS 的两段性和单调性,这样的话就保证我们第一次遍历到终点的时候与起点的距离(边的权重之和)是最小的。
这个双端队列广搜本质上就是一个简化版的dijkstra()算法,可以将队列看成一个小根堆,因为 BFS 的单调性,可以知道每次出队都相当于从堆拿出一个距离起点最小的点 $t$ 来更新其他点到起点的距离。因为同一个点可能会被其他点更新多次,所以在用 $t$ 更新其他点的时候的时候,需要判断 $d_t < dis_{a, b}$是否成立,如果成立,才能更新。
求偏移量的辅助图
#include <iostream>
#include <deque>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N = 510;
typedef pair<int, int>PII;
int n, m;
bool st[N][N];
char g[N][N];
int d[N][N];
//顺时针列出每个对角线方向上的信息
//网格上的点往四条对角线的点的偏移量
int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};
//网格上的点往四个对角线方向的网格的偏移量
int ix[] = {-1, -1, 0, 0}, iy[] = {-1, 0, 0, -1};
//四条对角线,当某次遍历对角线与下次要更新的点对应的对角线不同
//说明需要一次操作,即转90度
char c[5] = "\\/\\/";
int bfs()
{
memset(st, false, sizeof st);
memset(d, 0x3f, sizeof d);
d[0][0] = 0;
deque<PII> q;
q.push_back({0, 0});
while(q.size())
{
auto t = q.front();
q.pop_front();
int x = t.x, y = t.y;
if(x == n && y == m) return d[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];
int ga = x + ix[i], gb = y + iy[i];
if(a < 0 || a > n || b < 0 || b > m) continue;
int w = (g[ga][gb] != c[i]);
int dis = d[x][y] + w;
if(dis < d[a][b])
{
d[a][b] = dis;
if(!w) q.push_front({a, b});
else q.push_back({a, b});
}
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--)
{
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> g[i];
if((n + m) & 1) cout << "NO SOLUTION" << endl;
else
{
cout << bfs() << endl;
}
}
return 0;
}