牛客题解-胖胖的牛牛

原题链接

思路

这道题实际上就是一个优先队列bfs，在思路上并没有过多需要解释的，但是却有一些细节需要注意。

细节

首先就是如何判断是否转弯了（因为要统计总共的转弯数量）。

我们在写地图bfs的时候，往往会用到两个数组：

constexpr int dx[] = {-1, 1, 0, 0};
constexpr int dy[] = {0, 0, -1, 1};

可以方便的使用for循环遍历，从而计算出当前节点的上下左右相邻结点的坐标

可以看出，下标为0时，(dx, dy)是(-1, 0)，向上走，同理，下标为1时向下走，下标为2时向左走，下标为3时向右走。

那么我们完全可以使用一个变量记录方向：

dir==0	向上
dir==1	向下
dir==2	向左
dir==3	向右

这样，就能让我们很方便的判断是否转弯，因为我们在bfs中，会有如下过程：

while (!que.empty()) {
    pre = que.top(); que.pop();
    ...
    for (int i = 0; i < 4; ++i) {
        nex.x = pre.x + dx[i];
        nex.y = pre.y + dy[i];
        if (nex.x < 0 || nex.x >= n || nex.y < 0 || nex.y >= n) continue;
        ...
    }
}

那么我们在试图向队列中加入新的结点时，直接比较此时for循环的i和当前节点记录的dir就可以了，如下：

while (!que.empty()) {
    pre = que.top(); que.pop();
    ...
    for (int i = 0; i < 4; ++i) {
        nex.x = pre.x + dx[i];
        nex.y = pre.y + dy[i];
        if (nex.x < 0 || nex.x >= n || nex.y < 0 || nex.y >= n) continue;
        ...
        if (pre.dir != -1 && pre.dir != i) 
            que.push({nex.x, nex.y, pre.cnt + 1, i});
        else 
            que.push({nex.x, nex.y, pre.cnt, i});
    }
}

还有另外一个细节，就是vis数组。

当bfs或dijsktra写多了，就会有一个惯性思维，会认为只要当前节点来过，就把vis设为true（在之后不会再访问这个节点了）。实际上vis数组的设计是为了“剪枝”，即便将这个节点再放入队列中，也不会使答案产生更新了，此时才把vis[x]设为true。所以一定要考虑清楚这道题在什么情况下，一个节点不会导致答案的更新。

对这道题来说，是只要当前节点来过了，就一定不会导致答案更新了吗？并不是，因为虽然我们每次从队列中取出的是当前转弯次数最少的节点，但是如果从当前节点到下一个节点x而得到的转弯次数，并不一定会比其他节点到节点x的转弯次数少，比如：

如果\(x_1\)和\(u_1\)转弯次数相同，然后从队列中取出的是\(u_1\)，那么明显可以看出，节点v会从\(u_1\)首先到达，但实际上从\(x_1\)到达才是转弯次数最少的。

所以，正确方案应该是：每次从队列中取出来的，是当前所有节点中转弯次数最少的，那么这个就一定是当前这个点的最少转弯次数了，此时将当前节点vis设为true。

AC代码

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

constexpr int dx[] = {-1, 1, 0, 0};
constexpr int dy[] = {0, 0, -1, 1};
int n;

struct Point {
	int x, y, cnt, dir;

	bool operator < (const Point& p) const {
		return cnt > p.cnt;
	}
};

struct Graph {
	string g[105];
	bool vis[105][105];
	

	void bfs(int x, int y) {
		Point pre = {x, y, 0, -1}, nex;
		priority_queue<Point> que; que.push(pre);

		while (!que.empty()) {
			pre = que.top(); que.pop();
			if (g[pre.x][pre.y] == 'B') {
				cout << pre.cnt << '\n';
				return;
			}
			vis[pre.x][pre.y] = true;
			for (int i = 0; i < 4; ++i) {
				nex.x = pre.x + dx[i];
				nex.y = pre.y + dy[i];
				if (nex.x < 0 || nex.x >= n || nex.y < 0 || nex.y >= n) continue;
				if (g[nex.x][nex.y] == 'x') continue;
				if (vis[nex.x][nex.y]) continue;
				if (pre.dir != -1 && pre.dir != i) 
					que.push({nex.x, nex.y, pre.cnt + 1, i});
				else 
					que.push({nex.x, nex.y, pre.cnt, i});
			}
		}
		cout << -1 << '\n';
	}
}gra;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		gra.g[i].resize(n);
		for (int j = 0; j < n; ++j) {
			cin >> gra.g[i][j];
		}
	}

	int sx, sy;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (gra.g[i][j] == 'A') {
				sx = i;
				sy = j;
				goto NEX;
			}
		}
	}
NEX:
	gra.bfs(sx, sy);

	return 0;
}

错误示例

while (!que.empty()) {
    pre = que.top(); que.pop();
    if (vis[pre.x][pre.y]) continue; vis[pre.x][pre.y] = true;
    if (g[pre.x][pre.y] == 'B') {
        cout << pre.cnt << '\n';
        return;
    }
    for (int i = 0; i < 4; ++i) {
        nex.x = pre.x + dx[i];
        nex.y = pre.y + dy[i];
        if (nex.x < 0 || nex.x >= n || nex.y < 0 || nex.y >= n) continue;
        if (g[nex.x][nex.y] == 'x') continue;
        if (pre.dir != -1 && pre.dir != i) 
            que.push({nex.x, nex.y, pre.cnt + 1, i});
        else 
            que.push({nex.x, nex.y, pre.cnt, i});
    }
}

while (!que.empty()) {
    pre = que.top(); que.pop();
    if (g[pre.x][pre.y] == 'B') {
        cout << pre.cnt << '\n';
        return;
    }
    for (int i = 0; i < 4; ++i) {
        nex.x = pre.x + dx[i];
        nex.y = pre.y + dy[i];
        if (nex.x < 0 || nex.x >= n || nex.y < 0 || nex.y >= n) continue;
        if (g[nex.x][nex.y] == 'x') continue;
        if (vis[nex.x][nex.y]) continue;
        if (pre.dir != -1 && pre.dir != i) 
            que.push({nex.x, nex.y, pre.cnt + 1, i});
        else 
            que.push({nex.x, nex.y, pre.cnt, i});
        vis[nex.x][nex.y] = true;
    }
}