Use BFS, Python, similar as Problem 200-Number of Islanders


  • 0
    W
    class Solution(object):
        def solve(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            n,m,setx=len(board),0,[]
            if n>=1:
                m=len(board[0])
            if m>=1:
                for i in range(n):
                    if board[i][0]=='O':
                        setx.append([i,0])
                        board[i][0]='#'
                    if board[i][m-1]=='O':
                        setx.append([i,m-1])
                        board[i][m-1]='#'
                for i in range(1,m-1):
                    if board[0][i]=='O':
                        setx.append([0,i])
                        board[0][i]='#'
                    if board[n-1][i]=='O':
                        setx.append([n-1,i])
                        board[n-1][i]='#'
            while setx:
                current=setx.pop()
                a,b=current[0],current[1]
                if 1<=a and board[a-1][b]=='O':
                    setx.append([a-1,b])
                    board[a-1][b]='#'
                if a<=(n-2) and board[a+1][b]=='O':
                    setx.append([a+1,b])
                    board[a+1][b]='#'
                if 1<=b and board[a][b-1]=='O':
                    setx.append([a,b-1])
                    board[a][b-1]='#'
                if (m-2)>=b and board[a][b+1]=='O':
                    setx.append([a,b+1])
                    board[a][b+1]='#'
            for i in range(n):
                for j in range(m):
                    if board[i][j]=='O':
                        board[i][j]='X'
                    elif board[i][j]=='#':
                        board[i][j]='O'

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.