把“初始朝上”和“初始朝右”两种可能同时打包成一个六维状态，用 BFS 求一套公共指令的最短长度。
OJ: luogu
题目 ID: P3610
难度:提高+/省选-
标签:BFS状态压缩最短路搜索网格
日期: 2026-06-20 23:05
题意
给一个 N x N 网格，E 表示空地，H 表示障碍。
奶牛从左下角出发，要走到右上角。
每次可以下达三种指令之一：
- 前进
- 左转
- 右转
如果前进会撞墙或撞障碍，她就停在原地。
但题目最关键的地方是：
- 她一开始可能面朝上
- 也可能面朝右
我们并不知道是哪一种，所以要找一套同一套指令，保证两种初始朝向都能到终点，并且总指令数最短。
思路
先看一个更直白的对照版本：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
const int INF = 1e9;
int n;
char grid[MAXN][MAXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
struct CowState {
int x, y, dir;
};
struct State {
CowState a, b;
};
map<tuple<int, int, int, int, int, int>, int> dista;
bool inside(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
bool is_goal(int x, int y) {
return x == 0 && y == n - 1;
}
CowState move_forward(CowState s) {
if (is_goal(s.x, s.y)) {
return s;
}
int nx = s.x + dx[s.dir];
int ny = s.y + dy[s.dir];
if (!inside(nx, ny) || grid[nx][ny] == 'H') {
return s;
}
s.x = nx;
s.y = ny;
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> grid[i];
}
queue<State> q;
State start;
start.a = {n - 1, 0, 0};
start.b = {n - 1, 0, 1};
tuple<int, int, int, int, int, int> key =
make_tuple(start.a.x, start.a.y, start.a.dir, start.b.x, start.b.y, start.b.dir);
dista[key] = 0;
q.push(start);
while (!q.empty()) {
State cur = q.front();
q.pop();
tuple<int, int, int, int, int, int> cur_key =
make_tuple(cur.a.x, cur.a.y, cur.a.dir, cur.b.x, cur.b.y, cur.b.dir);
int now = dista[cur_key];
if (is_goal(cur.a.x, cur.a.y) && is_goal(cur.b.x, cur.b.y)) {
cout << now << '\n';
return 0;
}
// 左转
State s1 = cur;
s1.a.dir = (s1.a.dir + 3) % 4;
s1.b.dir = (s1.b.dir + 3) % 4;
tuple<int, int, int, int, int, int> k1 =
make_tuple(s1.a.x, s1.a.y, s1.a.dir, s1.b.x, s1.b.y, s1.b.dir);
if (!dista.count(k1)) {
dista[k1] = now + 1;
q.push(s1);
}
// 右转
State s2 = cur;
s2.a.dir = (s2.a.dir + 1) % 4;
s2.b.dir = (s2.b.dir + 1) % 4;
tuple<int, int, int, int, int, int> k2 =
make_tuple(s2.a.x, s2.a.y, s2.a.dir, s2.b.x, s2.b.y, s2.b.dir);
if (!dista.count(k2)) {
dista[k2] = now + 1;
q.push(s2);
}
// 前进
State s3 = cur;
s3.a = move_forward(s3.a);
s3.b = move_forward(s3.b);
tuple<int, int, int, int, int, int> k3 =
make_tuple(s3.a.x, s3.a.y, s3.a.dir, s3.b.x, s3.b.y, s3.b.dir);
if (!dista.count(k3)) {
dista[k3] = now + 1;
q.push(s3);
}
}
return 0;
}brute.cpp 直接把两种初始朝向同时放进一个 BFS 状态，用 map + tuple 记距离。
这个版本已经足够正确，但正式解可以把状态数组写得更紧凑一些。
关键观察是：
题目不是让我们分别为“朝上”和“朝右”各求一条路径，而是要求同一套指令同时适用于这两种情况。
所以最自然的状态不是单头牛的：
text
(x, y, dir)而是把两种可能同时打包：
text
(x1, y1, dir1, x2, y2, dir2)其中：
(x1, y1, dir1)表示“如果初始朝上，现在会是什么状态”(x2, y2, dir2)表示“如果初始朝右，现在会是什么状态”
每次操作会同时作用在这两个子状态上：
- 左转：两个方向都左转
- 右转：两个方向都右转
- 前进：两个状态都尝试前进一步；若撞墙或撞障碍，则留在原地
还有一个细节：
如果某个子状态已经到达终点，那么后续指令会被忽略，所以它保持在原地不动。
由于每条指令代价都是 1，所以直接对这个大状态做 BFS 即可。
当我们第一次到达：
text
两个子状态都在终点时，当前层数就是最短答案。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
const int INF = 1e9;
int n;
char grid[MAXN][MAXN];
// 方向顺序：0=上, 1=右, 2=下, 3=左
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
struct State {
int x1, y1, d1;
int x2, y2, d2;
};
int dista[MAXN][MAXN][4][MAXN][MAXN][4];
bool inside(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
bool blocked(int x, int y) {
return !inside(x, y) || grid[x][y] == 'H';
}
bool is_goal(int x, int y) {
return x == 0 && y == n - 1;
}
// 按当前朝向前进一步；如果撞墙或撞干草堆，就停在原地。
void move_forward(int x, int y, int dir, int &nx, int &ny) {
if (is_goal(x, y)) {
nx = x;
ny = y;
return;
}
int tx = x + dx[dir];
int ty = y + dy[dir];
if (blocked(tx, ty)) {
nx = x;
ny = y;
} else {
nx = tx;
ny = ty;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> grid[i];
}
for (int x1 = 0; x1 < n; x1++) {
for (int y1 = 0; y1 < n; y1++) {
for (int d1 = 0; d1 < 4; d1++) {
for (int x2 = 0; x2 < n; x2++) {
for (int y2 = 0; y2 < n; y2++) {
for (int d2 = 0; d2 < 4; d2++) {
dista[x1][y1][d1][x2][y2][d2] = INF;
}
}
}
}
}
}
queue<State> q;
// 起点在左下角。题目说初始朝向可能是“上”或“右”，
// 所以我们同时维护这两种状态。
State start = {n - 1, 0, 0, n - 1, 0, 1};
dista[start.x1][start.y1][start.d1][start.x2][start.y2][start.d2] = 0;
q.push(start);
while (!q.empty()) {
State cur = q.front();
q.pop();
int now = dista[cur.x1][cur.y1][cur.d1][cur.x2][cur.y2][cur.d2];
if (is_goal(cur.x1, cur.y1) && is_goal(cur.x2, cur.y2)) {
cout << now << '\n';
return 0;
}
// 操作 1：左转
State next1 = cur;
next1.d1 = (next1.d1 + 3) % 4;
next1.d2 = (next1.d2 + 3) % 4;
if (dista[next1.x1][next1.y1][next1.d1][next1.x2][next1.y2][next1.d2] == INF) {
dista[next1.x1][next1.y1][next1.d1][next1.x2][next1.y2][next1.d2] = now + 1;
q.push(next1);
}
// 操作 2：右转
State next2 = cur;
next2.d1 = (next2.d1 + 1) % 4;
next2.d2 = (next2.d2 + 1) % 4;
if (dista[next2.x1][next2.y1][next2.d1][next2.x2][next2.y2][next2.d2] == INF) {
dista[next2.x1][next2.y1][next2.d1][next2.x2][next2.y2][next2.d2] = now + 1;
q.push(next2);
}
// 操作 3：前进
State next3 = cur;
move_forward(cur.x1, cur.y1, cur.d1, next3.x1, next3.y1);
move_forward(cur.x2, cur.y2, cur.d2, next3.x2, next3.y2);
if (dista[next3.x1][next3.y1][next3.d1][next3.x2][next3.y2][next3.d2] == INF) {
dista[next3.x1][next3.y1][next3.d1][next3.x2][next3.y2][next3.d2] = now + 1;
q.push(next3);
}
}
return 0;
}复杂度
状态数最多是：
N * N * 4 * N * N * 4
每个状态只会入队一次，并扩展 3 条边，所以时间复杂度是：
空间复杂度同样是：
总结
这题的核心不是普通网格最短路，而是要看出：
- 不确定初始朝向
- 等价于同时维护两种可能
- 同一条指令要同步作用在两个子状态上
把这两种可能打包成一个 BFS 状态以后，问题就会变得非常直接。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
