poj 1321 排兵布阵问题 dfs算法

POJ 1321 排兵布阵问题可以使用 DFS 算法求解。

题目要求在一个 n x n 的棋盘上，放置 k 个棋子，其中每行、每列都最多只能有一个棋子。我们可以使用 DFS 枚举每个棋子的位置，对于每个棋子，尝试将其放置在每一行中未被占用的位置上，直到放置了 k 个棋子。在 DFS 的过程中，需要记录每行和每列是否已经有棋子，以便在尝试放置下一个棋子时进行判断。

以下是基本的 DFS 模板代码：

def dfs(row, cnt):
    global ans
    
    if cnt == k:
        ans += 1
        return
    
    for i in range(row, n):
        for j in range(n):
            if row_used[i] or col_used[j] or board[i][j] == '.':
                continue
            
            row_used[i] = col_used[j] = True
            dfs(i + 1, cnt + 1)
            row_used[i] = col_used[j] = False

n, k = map(int, input().split())
board = [input() for _ in range(n)]

row_used = [False] * n
col_used = [False] * n
ans = 0

dfs(0, 0)

print(ans)

其中，row 代表当前尝试放置棋子的行数，cnt 代表已经放置的棋子数量。row_used 和 col_used 分别表示每行和每列是否已经有棋子，board 则表示棋盘的状态。在尝试放置棋子时，需要排除掉无法放置的位置，即已经有棋子的行和列，以及棋盘上标记为 '.' 的位置。当放置了 k 个棋子时，即可计数一次方案数。注意，在回溯时需要将之前标记为已使用的行和列重新标记为未使用。

需要注意的是，在 Python 中，递归深度的默认限制为 1000，可能无法通过本题。可以通过以下代码来解除限制：

import sys

sys.setrecursionlimit(100000)

完整代码如下：