usaco-5.2.1 蜗牛的旅行

题目描述

$N \times N$ 的棋盘上有 $B$ 个路障，蜗牛从左上角 A1 出发，起步只能向右或向下；选定方向就直行到底，撞到棋盘边缘或路障时才转 90°（左转、右转任选），若撞到自己走过的格子则整段散步立即结束。求能走过的最多格子数（起点计入， $1<N<120$ ， $1\le B\le200$ ）。输入第一行 N B，随后 $B$ 行路障坐标（如 E2，字母为列、数字为行）；样例输入 8 4 / E2 / A6 / G1 / F5，输出 33。

思路

主动的选择只有起步方向（右或下）和每个撞墙点的左/右转向，于是把"起步方向 + 每次撞墙的转向"当成决策树回溯枚举：直行段按规则被动走到底，并沿途刷新走过的最大格数。撞上自己的足迹要立即结束、不再转弯；足迹属于单条分支，回溯时必须撤销。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 07:38
# update_at: 2026-10-01 07:38

import sys

DR = (-1, 0, 1, 0)  # 北、东、南、西四个方向的行偏移
DC = (0, 1, 0, -1)  # 北、东、南、西四个方向的列偏移
UNDO = 0  # 栈帧类型：回退帧，撤销一段直行的足迹并还原计数
WALK = 1  # 栈帧类型：直行帧，从 (row, col) 沿 dir 直行到底后再左右转弯


def solve() -> None:
    data = iter(sys.stdin.read().split())
    N = int(next(data))
    B = int(next(data))

    blocked = bytearray(N * N)  # 路障占用表，下标 = 行 * N + 列
    for _ in range(B):
        pos = next(data)
        col = ord(pos[0]) - 65  # 列字母 A1 的 A → 0
        row = int(pos[1:]) - 1  # 行号 A1 的 1 → 0
        blocked[row * N + col] = 1

    trail = bytearray(N * N)  # 当前路线已经走过的格子
    trail[0] = 1  # 出发点 A1 已计入
    count = 1
    ans = 1

    # 手写栈代替深递归：直行帧 (WALK, row, col, dir)，回退帧 (UNDO, 本段足迹下标)
    stack: list[tuple] = [(WALK, 0, 0, 1), (WALK, 0, 0, 2)]  # 初始只能向东或向南

    while stack:
        frame = stack.pop()
        if frame[0] == UNDO:
            for idx in frame[1]:
                trail[idx] = 0  # 回溯：撤掉这一段直行的足迹
            count -= len(frame[1])
            continue

        _, row, col, d = frame
        run: list[int] = []
        hit_trail = False  # 撞上自己的足迹：题目规定此时整段散步结束，不再转弯
        # 选定方向后一直走，直到棋盘边缘、路障或自己的足迹
        while True:
            nr, nc = row + DR[d], col + DC[d]
            if not 0 <= nr < N or not 0 <= nc < N:
                break
            idx = nr * N + nc
            if trail[idx]:
                hit_trail = True
                break
            if blocked[idx]:
                break
            trail[idx] = 1
            run.append(idx)
            row, col = nr, nc
            count += 1
        if count > ans:
            ans = count

        stack.append((UNDO, run))  # 子树全部结束后再统一撤销本段足迹
        if hit_trail:
            continue  # 撞到自己的足迹，无路可走，直接回溯
        # 只有撞边缘 / 路障才转弯：左转与右转都试，下一步走得通才入栈
        for nd in ((d + 1) % 4, (d + 3) % 4):
            nr, nc = row + DR[nd], col + DC[nd]
            if 0 <= nr < N and 0 <= nc < N and not trail[nr * N + nc] and not blocked[nr * N + nc]:
                stack.append((WALK, row, col, nd))

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:38
 * update_at: 2026-10-06 10:38
 */

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

typedef long long ll;

const int MAXN = 130;

int N, B;
char blocked[MAXN][MAXN]; // blocked[row][col] = 1 表示该格是路障
char trail[MAXN][MAXN];   // 当前这条路线已经走过的格子

// 四个方向的行列偏移：北、东、南、西
int DR[4] = {-1, 0, 1, 0};
int DC[4] = {0, 1, 0, -1};

const int UNDO = 0; // 栈帧类型：回退帧，撤销一段直行留下的足迹
const int WALK = 1; // 栈帧类型：直行帧，从 (row, col) 沿 dir 直行到底

// 一行直行是一个栈帧；用显式栈代替深递归，避免路线太长时爆栈
struct Frame {
    int type;
    int row;
    int col;
    int dir;
    int run_len; // 回退帧需要撤销的格子数
};

int count_cells; // 当前路线已经走过的格子数
int answer;      // 目前为止能走过的最多格子数

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

    cin >> N >> B;

    // 路障坐标形如 E2：字母是列（A 起），数字是行（1 起）
    for (int i = 0; i < B; i++) {
        string pos;
        cin >> pos;
        int col = pos[0] - 'A';
        int row = 0;
        int len = pos.size();
        for (int j = 1; j < len; j++) {
            row = row * 10 + (pos[j] - '0');
        }
        blocked[row - 1][col] = 1;
    }

    trail[0][0] = 1;
    count_cells = 1;
    answer = 1;

    vector<Frame> stk;
    // 起步只能向右（东）或向下（南）
    stk.push_back(Frame{WALK, 0, 0, 1, 0});
    stk.push_back(Frame{WALK, 0, 0, 2, 0});

    while (!stk.empty()) {
        Frame f = stk.back();
        stk.pop_back();

        if (f.type == UNDO) {
            // 撤销这一段直行的足迹：从起点沿原方向走 run_len 格逐格清空
            int r = f.row;
            int c = f.col;
            for (int k = 0; k < f.run_len; k++) {
                r += DR[f.dir];
                c += DC[f.dir];
                trail[r][c] = 0;
            }
            count_cells -= f.run_len;
            continue;
        }

        int r = f.row;
        int c = f.col;
        int d = f.dir;
        int run_len = 0;
        int hit_trail = 0; // 撞上自己的足迹：题目规定此时整段散步结束，不再转弯
        // 选定方向后一直走，直到棋盘边缘、路障或自己的足迹
        while (true) {
            int nr = r + DR[d];
            int nc = c + DC[d];
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) break;
            if (blocked[nr][nc]) break;
            if (trail[nr][nc]) {
                hit_trail = 1;
                break;
            }
            trail[nr][nc] = 1;
            run_len++;
            r = nr;
            c = nc;
        }
        count_cells += run_len;
        if (count_cells > answer) answer = count_cells;

        // 先压入回退帧，等这棵子树的兄弟分支都跑完，再统一撤销本段足迹
        stk.push_back(Frame{UNDO, f.row, f.col, d, run_len});

        if (hit_trail) continue; // 撞到自己的足迹，无路可走，直接回溯

        // 只有撞边缘或路障才转弯：左转、右转都试，第一步走得通才入栈
        int nd = (d + 1) % 4;
        int nr = r + DR[nd];
        int nc = c + DC[nd];
        if (nr >= 0 && nr < N && nc >= 0 && nc < N && !blocked[nr][nc] && !trail[nr][nc]) {
            stk.push_back(Frame{WALK, r, c, nd, 0});
        }
        nd = (d + 3) % 4;
        nr = r + DR[nd];
        nc = c + DC[nd];
        if (nr >= 0 && nr < N && nc >= 0 && nc < N && !blocked[nr][nc] && !trail[nr][nc]) {
            stk.push_back(Frame{WALK, r, c, nd, 0});
        }
    }

    cout << answer << endl;

    return 0;
}

usaco-5.2.1 蜗牛的旅行

目录

题目描述

思路

参考代码