• 又一个经典错误；来自某位同学
• 同样试一试下面的数据

3
A . .
. . .
x . B

• 答案是 1

#include<bits/stdc++.h>
using namespace std;
long long n, ax, ay, bx = -1, by = -1, x, y, xs, ys, p = 0;
long long sxy[210][210], sx[10] = {-1, 1, 0, 0}, sy[10] = {0, 0, -1, 1};
char a[210][210];
queue<pair<long long, long long >> q;
int main() {
	memset(sxy, -1, sizeof(sxy));
	cin >> n;
	for (long long i = 0; i < n; i++) {
		for (long long j = 0; j < n; j++) {
			cin >> a[i][j];
			if (a[i][j] == 'A') {
				ax = i;
				ay = j;
				q.push(make_pair(ax, ay));
				sxy[i][j] = 0;
			}
			if (a[i][j] == 'B') {
				bx = i;
				by = j;
			}
		}
	}
	if (bx == -1) {
		cout << -1 << endl;
		return 0;
	}
	while (!q.empty()) {
		x = q.front().first, y = q.front().second;
		q.pop();
		for (long long t = 0; t < 4; t++) {
			xs = x + sx[t];
			ys = y + sy[t];
			while (xs >= 0 && xs < n && ys >= 0 && ys < n) {
				if (sxy[xs][ys] != -1 || a[xs][ys] == 'x') break;
				q.push(make_pair(xs, ys));
				sxy[xs][ys] = sxy[x][y] + 1;
				xs += sx[t];
				ys += sy[t];
			}
		}
	}
	if (sxy[bx][by] < 0) cout << -1 << endl;
	else cout << sxy[bx][by] - 1 << endl;
	return 0;
}

• 经典错误：状态变为 dp[i][j][p] 表示从起点到 (i, j) 且最后方向为 p 的最少拐弯次数
• wrong answer
• 看下这个样例

3
A . .
. . .
x . B

• 答案是 1

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

using p3i = tuple<int, int, int>;

// 表示一个很大的数
const int inf = 1000000000;

// 在地图 g 中寻找 (sx, sy) 到 (ex, ey) 的字典序最小的最短路
int getPath(vector<vector<char>>& g, int sx, int sy, int ex, int ey) {
	// h: 地图的高, w: 地图的宽
	int h = g.size(), w = g[0].size();
	
	// 按字典序从小到大, D < L < R < U
	vector<int> dx = {1,  0, 0, -1};
	vector<int> dy = {0, -1, 1,  0};
	vector<string> f = {"D", "L", "R", "U"};
	
	// d[i][j][p] 表示从起点到 (i, j) 且最后方向为 p 的最短路, 初值为无穷大
	vector<vector<vector<int>>> d(h, vector<vector<int>>(w, vector<int>(4, inf)));
	
	queue<p3i> q;
	for (int i = 0; i < 4; i++) d[sx][sy][i] = 0, q.push({sx, sy, i});  // 初始方向不确定
	
	while (!q.empty()) {
		auto [x, y, p] = q.front();  // 取队首
		
		q.pop();                  // 将队首弹出
		for (int k = 0; k < 4; k++) {
			int u = x + dx[k], v = y + dy[k];
			if (u < 0 || u >= h || v < 0 || v >= w) continue;
			if (g[u][v] == 'x') continue;  // 障碍
			if (d[u][v][k] != inf) continue;
			
			// k 和 p 相不用拐弯, +0; 否则要拐弯 + 1
			int tmp = d[x][y][p] + (p != k);
			d[u][v][k] = tmp;  // 更新 d[u][v][k]
			q.push({u, v, k});
		}
	}
	int ans = inf;
	// 到达终点时 4 个方向都有可能
	for (int i = 0; i < 4; i++) ans = min(ans, d[ex][ey][i]);
	if (ans == inf) ans = -1;
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	// h: 地图的高, w: 地图的宽
	int h, w, sx, sy, ex, ey;
	cin >> h; w = h;
	vector<vector<char>> g(h, vector<char>(w));
	for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
		cin >> g[i][j];
		if (g[i][j] == 'A') sx = i, sy = j;
		if (g[i][j] == 'B') ex = i, ey = j;
	}
	cout << getPath(g, sx, sy, ex, ey) << '\n';
	
	return 0;	
}