优先队列版的代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[505][505];
int xl[4]={-1,1,-1,1};
int yl[4]={-1,1,1,-1};
int cxl[4]={0,1,0,1};
int cyl[4]={0,1,1,0};
char cl[4]={'\\','\\','/','/'};
struct node
{
	int x,y,c;
	bool operator < (const node nxt)const
	//优先队列小的放前面 
	{
		return c>nxt.c;
	}
};
priority_queue<node>q;
int dis[505][505];
void bfs()
{
	q.push({0,0,0});
	memset(dis,0x3f,sizeof dis);
	dis[0][0]=0;
	while(!q.empty())
	{
		int x=q.top().x;
		int y=q.top().y;
		int c=q.top().c;
		q.pop();
		if(x==n && y==m)
		{
			cout<<c;
			return;
		}
		for(int i=0;i<4;i++)
		{
			int xs=x+xl[i];
			int ys=y+yl[i];
			if(xs<0 || xs>n || ys<0 || ys>m)continue;
			int cs=c+((a[x+cxl[i]][y+cyl[i]]==cl[i])?0:1);
			if(cs<dis[xs][ys])
				dis[xs][ys]=cs,q.push({xs,ys,cs});
		}
	}
	cout<<"NO SOLUTION";
}
int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	bfs();
	return 0;
}

我给出一个要点，提醒此题与BFS模板的不同之处，也很考验对BFS的理解。希望大家也能在做题过程中总结出对自己有启发的经验教训。

提醒：某个交叉点第一次被访问时，到达该点的步数（旋转元件的次数）不一定是最小值，可能从其他路径过来的旋转次数更小，所以不能简单地用布尔型的vis数组标记并且跳过之前已被访问的点。

#include <bits/stdc++.h>
using namespace std;

struct pos {
	int x, y; // 【交叉点】的坐标
};
const int N = 520;
int n, m, ans = 0x7fffffff;
int steps[N][N]; // steps[i][j]记录走到点(i,j)花的最少旋转次数。
char mp[N][N];
bool vis[N][N];

// 从某个交叉点出发，只能往四个斜的方向走
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, -1, 1};
// 上面方向数组对应的斜线方向
char dir[4] = {'\\', '/', '/', '\\'};
// 因为要比对电线方向，所以可对应上面四个斜方向，
// 提前计算出要比对的mp数组的哪一格。
// 交叉点坐标从 0 开始，mp数组从 1 开始。
// 例如：交叉点 (1,1) 往左上走的那个格子坐标是 (1,1)。
int sx[4] = {0, 0, 1, 1}, sy[4] = {0, 1, 0, 1};

bool check(int x, int y) {
	return x >= 0 && y >= 0 && x <= n && y <= m;
}

deque<pos> q;
void bfs(pos src) {
	q.push_back(src);
	vis[0][0] = 1;
	while (!q.empty()) {
		pos node = q.front();
		q.pop_front();
//		cout << node.x << '\t' << node.y << '\n';
//		if (node.x == n && node.y == m) {
//			ans = min(ans, steps[node.x][node.y] );
//		}
		// 扩展：往四个斜方向走
		for (int i = 0; i < 4; i++) {
			int newx = node.x + dx[i];
			int newy = node.y + dy[i];
			if (!check(newx, newy)) continue;

			// 注意交叉点的坐标跟格子的坐标是不同的
			int newsx = node.x + sx[i];
			int newsy = node.y + sy[i];
			// 如果电线方向不对，那就需要旋转一次
			if (dir[i] != mp[newsx][newsy]) {
				// 如果当前这个方案的步数比之前搜出来的结果小，
				// 那就入队，覆盖之前的结果
				if (steps[node.x][node.y] + 1 < steps[newx][newy]) {
					steps[newx][newy] = steps[node.x][node.y] + 1;
					q.push_back({newx, newy});
				}
			} else {
				if (steps[node.x][node.y] < steps[newx][newy]) {
					steps[newx][newy] = steps[node.x][node.y];
					q.push_front({newx, newy});
				}
			}
			vis[newx][newy] = 1;
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> mp[i][j];

	// 只走对角线，那么“起点行列号之和的奇偶性”与
	// “终点行列号之和的奇偶性”相同。而起点是 (0,0)。
	if ((n + m) & 1) {
		cout << "NO SOLUTION";
		return 0;
	}

	// 初始化计步数组
	memset(steps, 0x3f, sizeof steps);
	steps[0][0] = 0;
	bfs({0, 0});
	cout << steps[n][m];

	return 0;
}