# 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的距離上

```python
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'

```python
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)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/dfs/general.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.