一道可以使用双端队列 BFS 做的最短路问题。
我们首先考虑建图：
- 对于每一个方格，如果它的方向是
，那么将它的左上角和右下角连一条长度为 (0) 的边，将它的左下角和右上角连一条长度为 (1) 的边； - 否则，如果它的方向是
/，那么将它的左上角和右下角连一条长度为 (1) 的边，将它的左下角和右上角连一条长度为 (0) 的边。
因此我们的最终答案就是 (dist_{n,m})。
考虑如何快速求出 (dist_{n,m})。
我们可以用一个双端队列，模拟 Dijkstra 算法的流程：
- 对于每一个点，向它的左上、右上、左下、右下方的点扩展。假设当前点是 ((i,j))。
- 然后，判断当前方格的方向是否连接当前节点和要扩展的节点。
- 如果是，那么将 (dist_{i,j}) 放到双端队列的队头。
- 否则，就将 (dist_{i,j}+1) 放到双端队列的队尾。
这样说可能会有一些难懂，具体的实现还需参考代码。
#include <bits/stdc++.h>
using namespace std;
const int N = 503;
const int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1}; //要扩展的点的偏移量
const int ix[] = {-1, -1, 0, 0}, iy[] = {-1, 0, 0, -1}; //当前节点对应的四个方格在输入的字符串中的偏移量
const char xk[] = "\/\/"; //能够正确连接当前节点与要扩展的点的电线方向
int n, m, t;
char s[N][N];
int vis[N][N], dist[N][N];
inline int bfs()
{
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
deque <pair <int, int> > q; //双端队列
q.push_front(make_pair(0, 0));
dist[0][0] = 0; //初始化
while (!q.empty())
{
int x = q.front().first, y = q.front().second;
q.pop_front();
if (x == n && y == m) return dist[x][y]; //到达了终点
if (vis[x][y]) continue;
vis[x][y] = 1;
for (int i = 0; i < 4; i+=1)
{
int xx = x + dx[i], yy = y + dy[i]; //要扩展的节点的横纵坐标
if (xx < 0 || xx > n || yy < 0 || yy > m) continue; //越界
int cx = x + ix[i], cy = y + iy[i]; //当前字符在输入字符串中的下标
int w = (xk[i] != s[cx][cy]); //方向是否正确
int d = dist[x][y] + w; //当前要旋转的最少次数
if (dist[xx][yy] >= d) //可以更新最少次数
{
dist[xx][yy] = d;
if (!w) q.push_front(make_pair(xx, yy)); //加到队头
else q.push_back(make_pair(xx, yy)); //加到队尾
}
}
}
return -1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i+=1) scanf("%s", s[i]);
if ((n + m) & 1) puts("NO SOLUTION"); //(n,m) 永远无法到达，那么直接输出无解
else cout << bfs() << endl;
return 0;
}