踩方格

题目描述

在无穷大的方格矩阵上从某点出发走 $n$ 步：每步走到相邻方格，只能向北、东、西三个方向走（不能向南），走过的格子立即塌陷、不能再走第二次；两种走法只要有一步不一样就算不同方案，求方案总数。

输入一个整数 $n$ （ $n \leqslant 20$ ），输出方案数量。样例：输入 2，输出 7。

思路

没有向南的走法，落点所在的最高一行只能被横走成一段连续区间，且落点是这段区间的端点。把落点压成两类：本行只有落点一格（可走北/东/西共 3 种）、本行已横走成段（只剩向北 + 唯一一侧横走共 2 种），线性递推 $a_k = a_{k-1} + b_{k-1}$ 、 $b_k = 2a_{k-1} + b_{k-1}$ ，答案 $f_n = a_n + b_n$ （初值 $a_0=1, b_0=0$ ，得 $f_2=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#!/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-09-29 23:04
# update_at: 2026-09-29 23:24

import sys


def solve() -> None:
    """走 n 步且不重复踩格的方案数：按当前端点的「本行是否横走过」分两类计数。"""
    n = int(sys.stdin.buffer.read())
    # 终点（最后一步的落点）总在最高的一行上，而这一行踩过的格子必是连续一段。
    # fresh：终点所在行只有它自己，向北/东/西都踩新格子（3 种走法）。
    # walked：终点所在行已有别的格子，终点是区间端点，只剩向北 + 唯一一侧的横走（2 种）。
    fresh, walked = 1, 0
    for _ in range(n):
        # 向北都只踏入全新的一行（两类都变 fresh）；横向走法数才是差别：
        # fresh 有 2 种、walked 只剩 1 种，都会让本行多踩一格（变 walked）。
        fresh, walked = fresh + walked, 2 * fresh + walked
    print(fresh + walked)


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/**
 * 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-05 05:18
 * update_at: 2026-10-05 05:18
 */

#include <cstdio>
typedef long long ll;

// 终点（最后一步的落点）总在最高的一行上，且该行被踩的格子是一段连续区间，落点是区间端点。
// fresh  ：本行只有落点这一格，向北/东/西都是新格子，共 3 种走法；
// walked ：本行已横走过一段，落点是端点，只剩向北 + 唯一一侧横走，共 2 种走法。
ll fresh;  // 走 k 步后落点在「本行只有一格」状态的方案数
ll walked; // 走 k 步后落点在「本行已横走成一段」状态的方案数

int main() {
    ll n; // 允许行走的步数，n <= 20
    scanf("%lld", &n);
    // 初值：还没走时只有起点，本行只有它自己
    fresh = 1;
    walked = 0;
    for (ll i = 1; i <= n; i++) {
        // 向北都踏入全新一行（两类都变 fresh）；fresh 有 2 种横走、walked 只剩 1 种，横走都变 walked
        ll nf = fresh + walked;   // 3 种走法里 1 种向北变 fresh：a' = a + b
        ll nw = 2 * fresh + walked; // 2 种横走变 walked：b' = 2a + b
        fresh = nf;
        walked = nw;
    }
    printf("%lld\n", fresh + walked);
    return 0;
}

目录

题目描述

思路

参考代码