M01321: 棋盘问题

dfs, http://cs101.openjudge.cn/practice/01321/

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放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

类似于n皇后问题的变种，可以使用回溯法来搜索所有可行的摆放方案

python

def place_pieces(n, k, row, board, cols, count):
    # 如果已经放置了k个棋子，计数加一
    if k == 0:
        count[0] += 1
        return
    
    # 从当前行row开始尝试
    for i in range(row, n):
        # 遍历该行所有列
        for j in range(n):
            # 如果当前位置是可放棋子的地方，并且没有放置在该列，且该行还没被用过
            if board[i][j] == '#' and not cols[j]:
                # 放置棋子，标记该行和该列
                cols[j] = 1
                place_pieces(n, k - 1, i + 1, board, cols, count)
                # 回溯，撤销棋子的放置
                cols[j] = 0

def main():
    while True:
        # 读取 n 和 k
        n, k = map(int, input().split())
        if n == -1 and k == -1:
            break
        
        # 读取棋盘形状
        board = [input().strip() for _ in range(n)]
        
        # 用来记录列的状态，0 表示该列没有放棋子，1 表示该列已放置棋子
        cols = [0] * n
        count = [0]  # 计数器，存储可行的方案数
        
        place_pieces(n, k, 0, board, cols, count)
        
        print(count[0])

if __name__ == "__main__":
    main()

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: 棋盘问题