[USACO06OCT] Cows on Skates G

题意

给出一个 r × c 的网格，其中：

. 表示可以走；
* 表示不能走。

从左上角 (1,1) 出发，每次可以走到上下左右四个相邻格子之一。题目保证一定存在至少一条路径到达右下角 (r,c)。

要求输出任意一条可行路径，并且步数不超过 10^5。

思路

最直接的想法，就是把网格当成一张无权图：

每个可走格子是一个点；
上下左右相邻的可走格子之间连边。

然后从起点做一次 BFS，第一次到达某个格子时，记下它是从哪个格子走过来的。

这个最直接、最适合帮助理解题意的版本如下：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95// brute.cpp：小数据直接 BFS 找一条路，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXR = 120;
const int MAXC = 80;

int r, c;
char g[MAXR][MAXC];
int vis[MAXR][MAXC];
int pre_x[MAXR][MAXC], pre_y[MAXR][MAXC];
int qx[MAXR * MAXC], qy[MAXR * MAXC];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool in_board(int x, int y) {
    return x >= 1 && x <= r && y >= 1 && y <= c;
}

void bfs() {
    memset(vis, 0, sizeof(vis));
    int head = 0, tail = 0;

    qx[tail] = 1;
    qy[tail] = 1;
    tail++;
    vis[1][1] = 1;
    pre_x[1][1] = 0;
    pre_y[1][1] = 0;

    while (head < tail) {
        int x = qx[head];
        int y = qy[head];
        head++;

        if (x == r && y == c) {
            return;
        }

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (!in_board(nx, ny)) {
                continue;
            }
            if (g[nx][ny] == '*') {
                continue;
            }
            if (vis[nx][ny]) {
                continue;
            }

            vis[nx][ny] = 1;
            pre_x[nx][ny] = x;
            pre_y[nx][ny] = y;
            qx[tail] = nx;
            qy[tail] = ny;
            tail++;
        }
    }
}

void print_path() {
    vector<pair<int, int> > path;
    int x = r, y = c;
    while (x != 0 && y != 0) {
        path.push_back(make_pair(x, y));
        int px = pre_x[x][y];
        int py = pre_y[x][y];
        x = px;
        y = py;
    }

    reverse(path.begin(), path.end());
    for (int i = 0; i < (int) path.size(); i++) {
        cout << path[i].first << ' ' << path[i].second << '\n';
    }
}

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

    cin >> r >> c;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> g[i][j];
        }
    }

    bfs();
    print_path();

    return 0;
}

为什么 BFS 足够

题目不要求最短路，只要求输出任意一条可行路径。

而 BFS 从起点出发，一旦访问到终点，就已经找到一条合法路径了。

同时，由于 BFS 记录的是父节点链，最终回溯出来的还是一条简单路径，不会出现重复绕圈，所以路径长度至多是格子数级别，远小于 10^5。

怎样恢复路径

设某个格子 (x,y) 第一次被访问时，是从 (px,py) 走过来的，那么就记录：

pre_x[x][y] = px
pre_y[x][y] = py

等 BFS 结束后，从终点 (r,c) 反向不断跳到父节点，直到回到起点 (1,1)，再把整条序列反转输出即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94#include <bits/stdc++.h>
using namespace std;

const int MAXR = 120;
const int MAXC = 80;

int r, c;
char g[MAXR][MAXC];
int vis[MAXR][MAXC];              // 是否访问过
int pre_x[MAXR][MAXC], pre_y[MAXR][MAXC]; // 记录路径上的父节点
int qx[MAXR * MAXC], qy[MAXR * MAXC];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool in_board(int x, int y) {
    return x >= 1 && x <= r && y >= 1 && y <= c;
}

void bfs() {
    memset(vis, 0, sizeof(vis));
    int head = 0, tail = 0;

    qx[tail] = 1;
    qy[tail] = 1;
    tail++;
    vis[1][1] = 1;
    pre_x[1][1] = 0;
    pre_y[1][1] = 0;

    while (head < tail) {
        int x = qx[head];
        int y = qy[head];
        head++;

        if (x == r && y == c) {
            return;
        }

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (!in_board(nx, ny)) {
                continue;
            }
            if (g[nx][ny] == '*') {
                continue;
            }
            if (vis[nx][ny]) {
                continue;
            }

            vis[nx][ny] = 1;
            pre_x[nx][ny] = x;
            pre_y[nx][ny] = y;
            qx[tail] = nx;
            qy[tail] = ny;
            tail++;
        }
    }
}

void print_path() {
    vector<pair<int, int> > path;
    int x = r, y = c;
    while (x != 0 && y != 0) {
        path.push_back(make_pair(x, y));
        int px = pre_x[x][y];
        int py = pre_y[x][y];
        x = px;
        y = py;
    }

    reverse(path.begin(), path.end());
    for (int i = 0; i < (int) path.size(); i++) {
        cout << path[i].first << ' ' << path[i].second << '\n';
    }
}

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

    cin >> r >> c;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> g[i][j];
        }
    }

    bfs();
    print_path();

    return 0;
}

复杂度

时间复杂度： $O(rc)$
空间复杂度： $O(rc)$

每个格子最多进队一次，每次只检查四个方向。

总结

这题本质就是最基础的网格 BFS 路径恢复。

核心只有两步：

BFS 找到终点；
用父节点数组把路径倒着找回来。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。