棋盘问题

题目描述

在一个给定形状的 $n \times n$ 棋盘（形状可能不规则）上摆放棋子，棋子没有区别。要求任意两个棋子不在同一行或同一列，求摆放 $k$ 个棋子的可行方案数 $C$ 。

输入含多组数据：每组第一行是两个正整数 $n, k$ （ $n \leqslant 8$ ， $k \leqslant n$ ），随后 $n$ 行每行 $n$ 个字符，# 表示棋盘区域、. 表示空白区域；以 -1 -1 结束输入。对每组数据输出一行方案数 $C$ （保证 $C < 2^{31}$ ）。样例：棋盘 #./.#、 $k=1$ 时输出 2；棋盘 ...#/..#./.#../#...、 $k=4$ 时输出 1。

思路

按行决策让"互不同行"自动成立：每行只有"不放"和"在某一列放一枚"两种选择。处理到第 $row$ 行时，未来只取决于哪些列已被占用，于是把列占用压成 $n$ 位掩码 $used$ （已放枚数即 $used$ 中 1 的个数），记忆化搜索 $count(row, used) = count(row+1, used) + \sum_{c \text{ 可放且空闲}} count(row+1, used \cup \{c\})$ 。剪枝： $used$ 已有 $k$ 个 1 时记 1 种方案，剩余行数 $n - row$ 小于还差枚数时记 0，总复杂度 $O(n^2 \cdot 2^n)$ 。

参考代码

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#!/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-30 00:03
# update_at: 2026-09-30 00:21

import sys
from functools import cache


@cache
def count(rows: tuple[int, ...], row: int, k: int, used: int) -> int:
    """第 row 行及以下放完剩余棋子、已占列集合为 used 时的方案数。

    每放一枚棋子必然占掉一列，所以"已经放了几枚"由 used 里 1 的个数决定，
    不必再单独传一个参数——这正是把状态从"摆到哪"换成"占了哪些列"的收益。
    """
    rest = k - used.bit_count()                   # 还差几枚棋子没放
    if rest == 0:
        return 1                                  # 棋子恰好放完：记一种方案
    if len(rows) - row < rest:
        return 0                                  # 剩下的行数不够摆，本分支作废
    free = rows[row] & ~used                      # 本行既能放、列又还空闲的位置
    return count(rows, row + 1, k, used) + sum(
        count(rows, row + 1, k, used | 1 << c)    # 本行在第 c 列摆一枚
        for c in range(len(rows))
        if free >> c & 1
    )


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    while True:
        n, k = int(next(data)), int(next(data))
        if n == -1 and k == -1:                   # 题面的输入结束标记
            break
        # 每行压成一个 n 位列掩码：第 c 位为 1 表示 (row, c) 是可放的 '#'
        rows = tuple(
            sum(1 << c for c, cell in enumerate(next(data).decode()) if cell == '#')
            for _ in range(n)
        )
        out.append(str(count(rows, 0, k, 0)))
        count.cache_clear()                       # 换棋盘就换命名空间，缓存不跨题累积
    print('\n'.join(out))


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/**
 * 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:50
 * update_at: 2026-10-05 05:50
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 8;      // n <= 8

int n, k;                // 棋盘边长与要摆的棋子数
ll ans;                  // 当前棋盘的方案数
ll rowMask[MAXN];        // rowMask[r]：第 r 行的 '#' 压成的 n 位掩码，第 c 位为 1 表示 (r,c) 可放

// 记忆化：memo[row][used] 表示第 row 行及以下、列占用掩码为 used 时的方案数
// -1 表示还没算过；每行至多一枚棋子，已放枚数就是 used 里 1 的个数
ll memo[MAXN + 1][1 << MAXN];
bool vis[MAXN + 1][1 << MAXN]; // 对应状态是否已算过

// 第 row 行及以下、列占用为 used 时，把剩余棋子放完的方案数
// 还差枚数 = k - used 中 1 的个数
ll dfs(int row, int used) {
    int rest = k - __builtin_popcount(used);
    if (rest == 0) return 1;                 // 棋子恰好放完：记 1 种方案
    if (n - row < rest) return 0;            // 剩余行数不够摆：剪枝
    if (vis[row][used]) return memo[row][used];

    ll res = dfs(row + 1, used);             // 本行不放棋子
    int freeMask = rowMask[row] & ~used;     // 本行可放且列还空闲的格子
    for (int c = 0; c < n; c++) {
        if (freeMask >> c & 1) {
            // 本行在第 c 列放一枚棋子
            res += dfs(row + 1, used | (1 << c));
        }
    }
    vis[row][used] = true;
    memo[row][used] = res;
    return res;
}

int main() {
    while (true) {
        scanf("%d %d", &n, &k);
        if (n == -1 && k == -1) break;       // 题面的输入结束标记

        for (int r = 0; r < n; r++) {
            char s[MAXN + 2];
            scanf("%s", s);
            rowMask[r] = 0;
            for (int c = 0; c < n; c++) {
                if (s[c] == '#') rowMask[r] |= 1LL << c;
            }
        }

        // 清空记忆化：不同棋盘不能共用状态
        for (int r = 0; r <= n; r++) {
            for (int m = 0; m < (1 << n); m++) vis[r][m] = false;
        }
        ans = dfs(0, 0);
        printf("%lld\n", ans);
    }
    return 0;
}

目录

题目描述

思路

参考代码