leetcode 51. N皇后
https://leetcode-cn.com/probl...
3つのタグ配列を定義します. colは、各カラムが占有されているかどうかを示し、ブールタイプ ul 2 dr左上から右下の斜線が占有されているかどうか、長さは2× n-1,アンダースケール変換:i=x-y+n-1,この斜線では横長座標の差が 固定されているため ur 2 dl右上から左下の斜線が占有されているかどうか、長さは2× n−1,下付きスケーリング:i＝x＋y,この対角線上では横長座標の和が固定された であるため
3つのタグ配列を定義します.
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
mp = [['.']*n for i in range(n)]
col = [False] * n
ul2dr = [0] * (n*2-1)
ur2dl = [0] * (n*2-1)
ans = []
def dfs(i):
if i == n:
ans.append([''.join(x) for x in mp])
for j in range(n):
pos1 = i - j + n - 1
pos2 = i + j
if not col[j] and ul2dr[pos1] == 0 and ur2dl[pos2] == 0: #
col[j] = True
ul2dr[pos1] += 1
ur2dl[pos2] += 1
mp[i][j] = 'Q'
dfs(i+1)
mp[i][j] = '.'
col[j] = False
ul2dr[pos1] -= 1
ur2dl[pos2] -= 1
dfs(0)
return ans