leetcode130. Surrounded Regions

题意：

130. Surrounded Regions

Medium

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.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

链接：

leetcode 130. Surrounded Regions

解题思路：

代码：

Java：

class Solution {public void solve(char[][] board) {if (board.length==0||board[0].length==0)    return;int n=board.length;int m=board[0].length;for(int i=0;i<n;++i){//左右两列if(board[i][0]=='O')    dfs(board,i,0);if(board[i][m-1]=='O')  dfs(board,i,m-1);}for(int i=0;i<m;++i){if(board[0][i]=='O')    dfs(board,0,i);if(board[n-1][i]=='O')  dfs(board,n-1,i);}for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(board[i][j]=='O')    board[i][j]='X';else if(board[i][j]=='Y')   board[i][j]='O';}}}private void dfs(char[][] board,int i,int j){if(i<0||j<0||i>=board.length||j>=board[0].length||board[i][j]!='O') return;if(board[i][j]=='O')    board[i][j]='Y';int[] dx=new int[]{1,-1,0,0};int[] dy=new int[]{0,0,-1,1};for(int t=0;t<4;++t){int x=i+dx[t];int y=j+dy[t];dfs(board,x,y);}}
}

Python3：

class Solution:def solve(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""if not board or not board[0]:   returnfor i in [0,len(board)-1]:for j in range(len(board[0])):self.dfs(board,i,j)for i in [0,len(board[0])-1]:for j in range(len(board)):self.dfs(board,j,i)for i in range(len(board)):for j in range(len(board[0])):if board[i][j]=='O':board[i][j]='X'elif board[i][j]=='Y':board[i][j]='O'def dfs(self,board,i,j):if 0 <= i < len(board) and 0 <= j < len(board[0]) and board[i][j] == 'O':board[i][j]='Y'dx=[-1,1,0,0]dy=[0,0,1,-1]for d in range(4):x=i+dx[d]y=j+dy[d]self.dfs(board,x,y)