深度优先搜索|130, 200

被围绕的区域

这个题应该是从外到里做，我们应该去找和外圈的’O’相通的所有’O’，而不是去找内圈被包围的’O’。
所以我们做的就是从边界的’O’出发，把和他相连的所有’O’都标为’A’，也就是说遍历到最后，没有被接触过的（还是’O’）的那些就一定是被包围的。
那么把所有标为’A’的（没有被包围的’O’）转回’O’；然后把所有没被碰过的’O’（被包围的）转成’X’。

class Solution:def solve(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""def direction(i,j,m,n):l = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]if i == 0:l.remove([i-1,j])if j == 0:l.remove([i,j-1])if i == m-1:l.remove([i+1,j])if j == n-1:l.remove([i,j+1])return lm = len(board)n = len(board[0])used = [[False]*n for _ in range(m)]def backtracking(i,j):if board[i][j] != 'O': return board[i][j] = 'A'l = direction(i,j,m,n)#print(i,j,l)#print(board)for k1,k2 in l:backtracking(k1,k2)for i in range(m):backtracking(i,0)backtracking(i,n-1)for j in range(n):backtracking(0,j)backtracking(m-1,j)for i in range(m):for j in range(n):if board[i][j] == 'A':board[i][j] = 'O'elif board[i][j] == 'O':board[i][j] = 'X'

岛屿数量

和上一题一样，从边界的岛开始一路往里找连接的岛，而且题目说的很清晰。

class Solution:def numIslands(self, grid: List[List[str]]) -> int:def direction(i,j,m,n):l = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]if i == 0:l.remove([i-1,j])if j == 0:l.remove([i,j-1])if i == m-1:l.remove([i+1,j])if j == n-1:l.remove([i,j+1])return lm = len(grid)n = len(grid[0])used = [[False]*n for _ in range(m)]def backtracking(i,j):if grid[i][j] == '0': returnused[i][j] = Truel = direction(i,j,m,n)for k1,k2 in l:if used[k1][k2]: continue backtracking(k1,k2)res = 0for i in range(m):for j in range(n):if used[i][j] or grid[i][j] == '0': continuebacktracking(i,j)res += 1return res