漫游小镇

形式化题目

$N \times N$ 网格（ $1 \le N \le 7$ ），起点在左上角、终点在左下角。求从起点出发恰好经过每个格子一次并到达终点的路径条数。

正解

思路

1. 朴素搜索与规模

这是哈密顿路径计数（NP-hard）， $N = 7$ 时 49 个格子的全排列搜索空间高达 $48!$ 量级，纯 DFS 必然爆炸。出路是强剪枝：每走一步都判断剩余局面是否还有解，尽早砍掉死枝。

2. 状态与增量维护

访问状态：每个格子一个 bit，49 格用一个 Python 整数 vis 表示，测试/更新都是 $O(1)$ 位运算；
度数表 deg[i]：格子 $i$ 的未访问邻居数，随访问增量维护；
度 0/1 集合：zeros（度 0）、ones（度 1）位掩码——这两个量是剪枝的核心信号。

3. 三大剪枝

区域切割：若当前格的左右均已封死（访问/越界）而上下都未访问（或反之），走出当前格后未访问区域被切成两半，永远走不遍 → 剪枝。
死胡同（度 1）：度 1 的内部格只能"一进一出"，若它不与当前格相邻，它将成为永远进不去/出不来的死角 → 剪枝；若恰有一个度 1 邻居，它就是唯一合法的下一步（强制步）。
度 0 / 集市隔绝：出现度 0 的内部格立即剪；终点集市若被未访问格隔离（与所有可走邻居不通）也剪。

加上「按度数小的邻居优先试」（尽早撞墙暴露死局），这套剪枝让 $N = 7$ 的搜索在时限内完成。

代码

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
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
131
132
133
134
135
136
137
138
139#!/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 08:20
# update_at: 2026-10-01 08:20

import sys

# N <= 7，网格至多 49 格：每个格子用一个 bit 表示"已访问"，整张棋盘就是 49 位整数，
# 剪枝用位运算一次测四个邻居，避免逐格检查。

def bits(mask: int):
    """依次产出 mask 中每个 1 位的下标。"""
    while mask:
        b = mask & -mask
        yield b.bit_length() - 1
        mask ^= b


def solve() -> None:
    n = int(sys.stdin.buffer.read())
    cells = n * n
    full = (1 << cells) - 1
    target = (n - 1) * n  # 左下角 = 集市

    # NB[i]：i 的四个邻居合并成的位掩码；SIDE[i] = (左, 右, 上, 下) 各是单比特掩码，越界记 0
    inb = lambda r, c: 0 <= r < n and 0 <= c < n
    NB = tuple(
        sum(1 << (nr * n + nc) for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)) if inb(nr, nc))
        for r in range(n) for c in range(n)
    )
    SIDE = tuple(
        tuple(1 << (nr * n + nc) if inb(nr, nc) else 0 for nr, nc in ((r, c - 1), (r, c + 1), (r - 1, c), (r + 1, c)))
        for r in range(n) for c in range(n)
    )
    PB = tuple(1 << i for i in range(cells))  # 单比特掩码表，避免反复 1 << i
    tbit = PB[target]

    # 增量维护每个未访问格的"度"（未访问邻居数），并登记度 0 / 度 1 的格子：
    # 度 0 的内部格永远到不了；度 1 的内部格只能紧贴当前格成为下一步，否则就是死胡同。
    deg = [NB[i].bit_count() for i in range(cells)]
    ones = sum(PB[i] for i in range(cells) if deg[i] == 1 and i != target)
    zeros = 0

    ans = 0

    def dfs(pos: int, vis: int, left: int) -> None:
        """从 pos 出发走遍剩余 left 格、终点为集市的路径计数（枚举所有哈密顿路径）。"""
        nonlocal ans, ones, zeros
        if pos == target:  # 走到集市：必须同时走完全部格子，否则剩下的格子永远到不了
            ans += left == 0
            return
        U = full ^ vis
        # 剪枝 1（孤立区域）：左右都已封死（访问过或越界）而上、下都未访问，或相反。
        # 步出当前格后未访问区域会被切成两半，永远走不完。
        l, r, u, d = SIDE[pos]
        l_vis = not l or (l & vis)
        r_vis = not r or (r & vis)
        u_vis = not u or (u & vis)
        d_vis = not d or (d & vis)
        if (l_vis and r_vis and not u_vis and not d_vis) or (u_vis and d_vis and not l_vis and not r_vis):
            return
        avail = NB[pos] & U
        if not avail:  # 无路可走
            return
        if not (avail & tbit) and deg[target] == 0:  # 集市已被未访问格隔离
            return
        if zeros:  # 存在度 0 的内部格
            return
        # 剪枝 2（死胡同）：度 1 的内部格必须与当前格相邻，否则它只有"一进"没有"一出"
        forced, only = 0, -1
        f = ones
        while f:
            b = f & -f
            w = b.bit_length() - 1
            if w != pos:
                if not (NB[pos] & b):
                    return
                forced += 1
                only = w
            f ^= b
        if forced > 1:  # 两个度 1 格不可能都成为下一步
            return
        if forced:  # 唯一度 1 邻居是唯一合法的下一步
            moves = (only,)
        else:
            moves = sorted((deg[x], x) for x in bits(avail))  # 度数小的先走，尽早撞墙
        for _, x in moves:
            if x == target and left > 1:
                continue
            # 访问 pos：邻居的度 -1，并同步维护 ones/zeros 两个登记表
            f = NB[pos] & U
            while f:
                b = f & -f
                w = b.bit_length() - 1
                deg[w] -= 1
                if w != target:
                    if deg[w] == 1:
                        zeros &= ~b
                        ones |= b
                    elif deg[w] == 0:
                        ones &= ~b
                        zeros |= b
                    else:
                        ones &= ~b
                        zeros &= ~b
                f ^= b
            ones &= ~PB[pos]
            zeros &= ~PB[pos]
            dfs(x, vis | PB[pos], left - 1)
            # 回溯：度 +1，恢复登记表（pos 本身按原度数归位）
            f = NB[pos] & U
            while f:
                b = f & -f
                w = b.bit_length() - 1
                deg[w] += 1
                if w != target:
                    if deg[w] == 1:
                        zeros &= ~b
                        ones |= b
                    elif deg[w] == 0:
                        ones &= ~b
                        zeros |= b
                    else:
                        ones &= ~b
                        zeros &= ~b
                f ^= b
            if deg[pos] == 1:
                ones |= PB[pos]
            elif deg[pos] == 0:
                zeros |= PB[pos]

    dfs(0, 1, cells - 1)
    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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194/**
 * 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 12:43
 * update_at: 2026-10-06 12:43
 */
// roj/2089 漫游小镇：N×N 网格的哈密顿路径计数（左上角农场 -> 左下角集市）。
// 做法：DFS + 位掩码维护访问状态 + 三大可行性剪枝（区域切割 / 度 1 死胡同 / 度 0 判死）。

#include <cstdio>

typedef long long ll;
typedef unsigned long long ull;

const int MAXC = 49; // N<=7，最多 7*7=49 个格子

int n;      // 网格边长
int cells;  // 格子总数 n*n
int target; // 集市（左下角）的格子编号

ull full;          // 全部格子都访问的掩码
ull tbit;          // 集市对应的单比特掩码
ull pb[MAXC];      // pb[i]：只含第 i 位的掩码，避免反复写 1<<i
ull nmask[MAXC];   // nmask[i]：i 的四个相邻格子组成的掩码（越界不计）
ull side[MAXC][4]; // side[i]：i 的左/右/上/下邻居的单比特掩码，越界记 0

int deg[MAXC]; // deg[i]：i 当前的未访问邻居数，随搜索增量维护
ull ones;      // 度恰好为 1 的未访问非集市格掩码，是「死胡同」剪枝的信号
ull zeros;     // 度为 0 的未访问非集市格掩码，一旦出现即无解

ll answer; // 路径条数

bool inGrid(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < n;
}

// 从 pos 出发、已访问集合为 vis、还剩 left 个格子未走时，走向集市的路径数。
void dfs(int pos, ull vis, int left) {
    if (pos == target) { // 走到集市：必须同时走完全部格子
        if (left == 0) answer++;
        return;
    }
    ull unvis = full ^ vis;

    // 剪枝 1（区域切割）：当前格左右都被封死（越界或已访问）而上下都未访问，
    // 或上下被封死而左右都未访问；走出当前格后未访问区域会被切成两半，永远走不完。
    ull l = side[pos][0], r = side[pos][1], u = side[pos][2], d = side[pos][3];
    bool lBlock = (l == 0) || ((l & vis) != 0);
    bool rBlock = (r == 0) || ((r & vis) != 0);
    bool uBlock = (u == 0) || ((u & vis) != 0);
    bool dBlock = (d == 0) || ((d & vis) != 0);
    if ((lBlock && rBlock && !uBlock && !dBlock) ||
        (uBlock && dBlock && !lBlock && !rBlock)) {
        return;
    }

    ull avail = nmask[pos] & unvis; // 当前格可走的未访问邻居
    if (avail == 0) return;         // 四面皆堵却还没走完

    // 集市与所有可走邻居都不相邻，且已无未访问邻居，将来无法进入。
    if ((avail & tbit) == 0 && deg[target] == 0) return;

    // 存在度 0 的非集市格：那个格子永远进不去也出不来。
    if (zeros != 0) return;

    // 剪枝 2（死胡同）：度 1 的格子只能「一进一出」，必须紧贴当前格成为下一步，
    // 否则它将成为死角；若同时出现两个度 1 格则无法都照顾到，直接剪掉。
    int forced = -1;
    int forcedCnt = 0;
    ull f = ones;
    while (f != 0) {
        int w = __builtin_ctzll(f);
        f &= f - 1;
        if (w == pos) continue;
        if ((nmask[pos] & pb[w]) == 0) return;
        forced = w;
        forcedCnt++;
    }
    if (forcedCnt > 1) return;

    // 组织候选下一步：有强制步就只走它；否则把可用邻居按度数小的优先枚举，
    // 尽早撞墙，从而更早触发剪枝。
    int moves[MAXC];
    int moveCnt = 0;
    if (forcedCnt == 1) {
        moves[moveCnt++] = forced;
    } else {
        int candDeg[MAXC];
        int candId[MAXC];
        int candCnt = 0;
        ull a = avail;
        while (a != 0) {
            int w = __builtin_ctzll(a);
            a &= a - 1;
            candDeg[candCnt] = deg[w];
            candId[candCnt] = w;
            candCnt++;
        }
        for (int i = 0; i < candCnt; i++) { // 选择排序：按度数升序
            int best = i;
            for (int j = i + 1; j < candCnt; j++) {
                if (candDeg[j] < candDeg[best]) best = j;
            }
            int td = candDeg[i];
            candDeg[i] = candDeg[best];
            candDeg[best] = td;
            int ti = candId[i];
            candId[i] = candId[best];
            candId[best] = ti;
            moves[i] = candId[i];
        }
        moveCnt = candCnt;
    }

    for (int mi = 0; mi < moveCnt; mi++) {
        int x = moves[mi];
        // 集市必须是最后一格，因此还剩多于一个格子时不能进集市。
        if (x == target && left > 1) continue;

        // 离开 pos：把 pos 当作已访问，它的每个未访问邻居度数 -1，并同步 ones/zeros。
        ull nb = nmask[pos] & unvis;
        ull t = nb;
        while (t != 0) {
            int w = __builtin_ctzll(t);
            t &= t - 1;
            deg[w]--;
            if (w != target) {
                if (deg[w] == 1) { zeros &= ~pb[w]; ones |= pb[w]; }
                else if (deg[w] == 0) { ones &= ~pb[w]; zeros |= pb[w]; }
                else { ones &= ~pb[w]; zeros &= ~pb[w]; }
            }
        }
        ones &= ~pb[pos];
        zeros &= ~pb[pos];

        dfs(x, vis | pb[pos], left - 1);

        // 回溯：恢复邻居度数以及 ones/zeros，再把 pos 按原度数重新登记。
        t = nb;
        while (t != 0) {
            int w = __builtin_ctzll(t);
            t &= t - 1;
            deg[w]++;
            if (w != target) {
                if (deg[w] == 1) { zeros &= ~pb[w]; ones |= pb[w]; }
                else if (deg[w] == 0) { ones &= ~pb[w]; zeros |= pb[w]; }
                else { ones &= ~pb[w]; zeros &= ~pb[w]; }
            }
        }
        if (deg[pos] == 1) ones |= pb[pos];
        else if (deg[pos] == 0) zeros |= pb[pos];
    }
}

int main() {
    scanf("%d", &n);
    cells = n * n;
    target = (n - 1) * n; // 左下角的编号
    full = (1ULL << cells) - 1;
    for (int i = 0; i < cells; i++) pb[i] = 1ULL << i;
    tbit = pb[target];

    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    for (int r = 0; r < n; r++) { // 预计算每个格子的邻居掩码和四向掩码
        for (int c = 0; c < n; c++) {
            int i = r * n + c;
            nmask[i] = 0;
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (inGrid(nr, nc)) nmask[i] |= pb[nr * n + nc];
            }
            side[i][0] = inGrid(r, c - 1) ? pb[r * n + c - 1] : 0;
            side[i][1] = inGrid(r, c + 1) ? pb[r * n + c + 1] : 0;
            side[i][2] = inGrid(r - 1, c) ? pb[(r - 1) * n + c] : 0;
            side[i][3] = inGrid(r + 1, c) ? pb[(r + 1) * n + c] : 0;
        }
    }

    ones = 0;
    zeros = 0;
    for (int i = 0; i < cells; i++) deg[i] = __builtin_popcountll(nmask[i]);
    for (int i = 0; i < cells; i++) { // 集市不参与度 1/0 的判定
        if (i == target) continue;
        if (deg[i] == 1) ones |= pb[i];
        else if (deg[i] == 0) zeros |= pb[i];
    }

    answer = 0;
    dfs(0, pb[0], cells - 1); // 起点是左上角
    printf("%lld\n", answer);
    return 0;
}

复杂度

时间复杂度：最坏仍是指数级（哈密顿计数固有的 NP 难度），但三大剪枝把实际搜索量压到可接受范围， $N = 7$ 实测秒级。
空间复杂度： $O(N^2)$ 的位掩码与度数表，递归栈 $O(N^2)$ 。

总结

哈密顿路径计数的标准姿势：DFS + 位掩码状态 + 可行性剪枝（切割/度 1 强制度 0 判死）。
度数增量维护是剪枝效率的关键：每次只更新当前格邻居的度，均摊 $O(1)$ 。
「强制步」剪枝（度 1 邻居必走）往往一次砍掉整棵分支，是本题最大的加速来源。

目录

形式化题目

正解

思路

1. 朴素搜索与规模

2. 状态与增量维护

3. 三大剪枝

代码

复杂度

总结