M01321: 棋盘问题

backtracking, http://cs101.openjudge.cn/pctbook/M01321/

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

输入

输入含有多组测试数据。每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出

2
1

来源：蔡错@pku

这个题是一个典型的 回溯搜索（DFS + 剪枝） 问题，类似于不规则棋盘上的「n 皇后」变形版：

棋盘是 n×n，但有些位置不可用（用 . 表示）。
要摆放 k 个棋子。
限制条件：任意两个棋子不能在同一行或同一列。
要输出所有可行方案的个数。

思路解析

状态表示
- 从第 row=0 行开始，一行一行往下考虑是否放棋子。
- 用一个布尔数组 used_col[j] 标记某一列是否已经放过棋子。
搜索分支
- 在第 row 行：
  - 可以选择不放棋子，继续搜索下一行。
  - 可以在这一行的某一列放棋子（前提是：该格是 #，并且该列还没用过），然后继续搜索下一行。
边界条件
- 如果已经放了 k 个棋子 → 计数 +1。
- 如果行数到头，还没放够 k → 剪枝返回。
复杂度
- n ≤ 8，搜索规模不大，DFS完全可行。

Python 实现

python

def solve():
    import sys
    sys.setrecursionlimit(10000)
    input_data = sys.stdin.read().splitlines()

    idx = 0
    while True:
        n, k = map(int, input_data[idx].split())
        idx += 1
        if n == -1 and k == -1:
            break

        board = [list(input_data[idx + i]) for i in range(n)]
        idx += n

        used_col = [False] * n
        res = 0

        def dfs(row, placed):
            nonlocal res
            if placed == k:
                res += 1
                return
            if row == n:
                return

            # 选择不在这一行放棋子
            dfs(row + 1, placed)

            # 在这一行某个可行位置放棋子
            for col in range(n):
                if board[row][col] == '#' and not used_col[col]:
                    used_col[col] = True
                    dfs(row + 1, placed + 1)
                    used_col[col] = False

        dfs(0, 0)
        print(res)

solve()

位运算优化版（把列状态用一个整数 bitmask 表示）核心思路是：用一个整数的二进制位来表示列是否被占用。这样就不需要维护 used_col[] 数组，速度和内存都会更快。

关键优化点

n ≤ 8，所以最多 8 列，可以用一个 int 的低 8 位 表示列状态。
- 第 j 位 = 1 → 第 j 列已放棋子。
- 第 j 位 = 0 → 第 j 列还可用。
搜索时，如果能放棋子，就把对应列位置 1，再递归。
回溯时直接恢复，不需要 used_col 数组。

Python 位运算版本

python

def solve():
    import sys
    sys.setrecursionlimit(10000)
    input_data = sys.stdin.read().splitlines()
    
    idx = 0
    while True:
        n, k = map(int, input_data[idx].split())
        idx += 1
        if n == -1 and k == -1:
            break

        board = [list(input_data[idx + i]) for i in range(n)]
        idx += n
        
        res = 0
        
        def dfs(row, placed, colmask):
            nonlocal res
            if placed == k:
                res += 1
                return
            if row == n:
                return
            
            # 这一行不放棋子
            dfs(row + 1, placed, colmask)
            
            # 尝试在这一行放一个棋子
            for col in range(n):
                if board[row][col] == '#' and not (colmask & (1 << col)):
                    dfs(row + 1, placed + 1, colmask | (1 << col))
        
        dfs(0, 0, 0)
        print(res)

solve()

python

# 石贤泽2300012407
def count_ways(board, n, k):
    def backtrack(row, columns):
        if len(columns) == k:
            return 1
        if row >= n:
            return 0
        count = 0
        for col in range(n):
            if board[row][col] == '#' and col not in columns :
                columns.add(col)
                count += backtrack(row + 1, columns)
                columns.remove(col)
        count += backtrack(row + 1, columns)    # 考虑不放置棋子的情况
        return count
    return backtrack(0, set())

while True:
    n, k = map(int, input().split())
    if n == -1 and k == -1:
        break
    board = [input() for j in range(n)]
    print(count_ways(board, n, k))

python

# https://www.cnblogs.com/Ayanowww/p/11555193.html
'''
本题知识点：深度优先搜索 + 枚举 + 回溯

题意是要求我们把棋子放在棋盘的'#'上，但不能把两枚棋子放在同一列或者同一行上，问摆好这k枚棋子有多少种情况。

我们可以一行一行地找，当在某一行上找到一个可放入的'#'后，就开始找下一行的'#'，如果下一行没有，就再从下一行找。这样记录哪个'#'已放棋子就更简单了，只需要记录一列上就可以了。
'''
n, k, ans = 0, 0, 0
chess = [['' for _ in range(10)] for _ in range(10)]
take = [False] * 10

def dfs(h, t):
    global ans

    if t == k:
        ans += 1
        return

    if h == n:
        return

    for i in range(h, n):
        for j in range(n):
            if chess[i][j] == '#' and not take[j]:
                take[j] = True
                dfs(i + 1, t + 1)
                take[j] = False

while True:
    n, k = map(int, input().split())
    if n == -1 and k == -1:
        break

    for i in range(n):
        chess[i] = list(input())

    take = [False] * 10
    ans = 0
    dfs(0, 0)
    print(ans)

M01321: 棋盘问题 ​

M01321: 棋盘问题