General

51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Example:

[
  // Solution 1
  [".Q..",
   "...Q",
   "Q...",
   "..Q."
  ],
  // Solution 2
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."
  ]
]

• 比較newRow不能在已有的垂直線上, row和newRow的距離上

def solveNQueens(self, n: int) -> List[List[str]]:
    ans = []
    self.dfs(0, n, [], ans)
    return ans

def dfs(self, row, n, cands, ans):
    if row == n:
        ans.append(self.build(cands))
        
    for idx in range(n):
        if self.isValid(cands,idx):
            # print(row)
            self.dfs(row+1, n, cands + [idx], ans)
        
def isValid(self, cands, idx):
    n = len(cands)
    for i in range(n):
        diff = abs(cands[i] - idx)
        if diff == 0 or diff == (n - i): # 跟第i層的距離
            return False
    return True

def build(self, cands):
    grid = []
    for idx in cands:
        line = ''
        for j in range(len(cands)):
            line += 'Q' if j == idx else '.'   
        grid.append(line)
    return grid

130. Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

• 掃描邊界，遇到'O', dfs翻成'*'

• 遍歷每一層，遇到'*'翻回'O', 遇到'O'翻成'X'

def solve(self, board: List[List[str]]) -> None:
    if not board: return
    
    self.m, self.n = len(board), len(board[0])
    # trasere the border and mark all 'o' to '#'
    for i in [0, self.m-1]:
        for j in range(self.n):
            if board[i][j] == 'O':
                self.dfs(i, j, board)      
    for i in range(1, self.m-1):
        for j in [0, self.n-1]:
            if board[i][j] == 'O':
                self.dfs(i, j, board)
                
    # mark 'O' to 'X', '#' to O
    for i in range(self.m):
        for j in range(self.n):
            if board[i][j] == '*':
                board[i][j] = 'O'
            elif board[i][j] == 'O':
                board[i][j] = 'X'
            

def dfs(self, i, j, board):
    board[i][j] = '*'
    
    for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        y = i + dy
        x = j + dx
        
        if not (0 <= y < self.m and 0 <= x < self.n): continue
        if board[y][x] == 'O':
            self.dfs(y, x, board)