【广度优先搜索-中等】130. 被围绕的区域

【题目】
【代码】
【方法1】
对矩阵的四条边进行遍历，对于边上“O”的点深度优先搜索，将预期相连的所有“O”点全部在原存储空间上标记为“A”点（或者其他除“O”、“X”之外的点）
处理完成之后，遍历矩阵的每个元素，对矩阵中所有标记为“A”点的还原成原来的“O”点
将“O”点替换成“X”点即可完成对被围绕区域的替换

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return
        def dfs(x,y):
            if not 0<=x<len(board) or not 0<=y<len(board[0]) or board[x][y]!="O":
                return
            board[x][y]="A"
            dfs(x-1,y)
            dfs(x+1,y)
            dfs(x,y+1)
            dfs(x,y-1)
        for i in range(len(board)):
            dfs(i,0)
            dfs(i,len(board[0])-1)
        for i in range(len(board[0])):
            dfs(0,i)
            dfs(len(board)-1,i)
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]=="A":
                    board[i][j]="O"
                elif board[i][j]=="O":
                    board[i][j]="X"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

【方法2】自创方法 时空复杂度都差很多

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        visited=[[0 for i in range(len(board[0]))] for i in range(len(board))]
        cnt=0
        def dfs(x,y):
            if x>=0 and x<len(board) and y>=0 and y<len(board[0]) and board[x][y]=="O" and visited[x][y]==0:
                if x==0 or x==(len(board)-1) or y==0 or y==(len(board[0])-1):
                    return False
                visited[x][y]=1
                self.tmp.append((x,y))
                ans1=dfs(x-1,y)
                ans2=dfs(x+1,y)
                ans3=dfs(x,y+1)
                ans4=dfs(x,y-1)
                return True and ans1 and ans2 and ans3 and ans4
            if x>=0 and x<len(board) and y>=0 and y<len(board[0]):
                return True
            return False
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]=="O" and visited[i][j]==0:
                    self.tmp=[]
                    res=dfs(i,j)
                    if res:
                        for x,y in self.tmp:
                            board[x][y]="X"
        return cnt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27