AcWing 843. n-皇后问题
原题链接
中等
作者:
kugua
,
2020-07-23 21:20:32
,
所有人可见
,
阅读 550
def dfs(u):
if u==n:
for i in range(n):
print("".join(path[i]))# 注意这里输出的方法,如果不加join会输出成矩阵
print()
return
for i in range(n):
if not lie[i] and not dj[n+i-u] and not fdj[u+i]: #注意u-i+n 和u+i
path[u][i] = 'Q'
fdj[i+u] =dj[n+i-u]= lie[i]=True
dfs(u+1)
fdj[i+u] =dj[n+i-u]= lie[i]=False
path[u][i] = '.'
n = int(input())
path = [(['.']*n) for i in range(n)]
#注意我这里之前写的[['.']*n]*n,这样写会让每行都受到一样的操作
N = 20
dj = N*[False]
fdj = N*[False]
lie = n*[False]
dfs(0)