In this Leetcode Surrounded Regions problem solution we have Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.
Problem solution in Python.
class Solution: def solve(self, board: List[List[str]]) -> None: point_set = set() def outside_border(i, j): if (i == 0 or i == len(board) - 1) or (j == 0 or j == len(board[i]) - 1): return True return False def dfs(i, j): point_set.add((i, j)) directions = [(0, 1), (1, 0), (-1, 0), (0, -1)] for direction in directions: new_x = i + direction[0] new_y = j + direction[1] if (0 <= new_x < len(board) and 0 <= new_y < len(board[i]) and board[new_x][new_y] == 'O' and (new_x, new_y) not in point_set): dfs(new_x, new_y) for i in range(len(board)): for j in range(len(board[i])): if board[i][j] == 'O' and outside_border(i, j): dfs(i, j) for i in range(len(board)): for j in range(len(board[i])): if board[i][j] == 'O' and (i , j) not in point_set: board[i][j] = 'X'
Problem solution in Java.
class Solution { public void solve(char[][] board) { if (board.length == 1 || board[0].length == 1) return; for (int i = 0; i < board[0].length; i++) { if (board[0][i] == 'O') visit(board, 0, i); if (board[board.length - 1][i] == 'O') visit(board, board.length - 1, i); } for (int i = 1; i < board.length - 1; i++) { if (board[i][0] == 'O') visit(board, i, 0); if (board[i][board[0].length - 1] == 'O') visit(board, i, board[0].length - 1); } for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (board[i][j] == 'Y') board[i][j] = 'O'; else board[i][j] = 'X'; } } } private void visit(char[][] board, int i, int j) { if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') return; board[i][j] = 'Y'; visit(board, i - 1, j); visit(board, i + 1, j); visit(board, i, j - 1); visit(board, i, j + 1); } }
Problem solution in C++.
class Solution { int rows,cols; vector<vector<bool>> vis; void dfs(vector<vector<char>>& board,int i,int j) { if(i<0||i>=rows||j<0||j>=cols||board[i][j]=='X'||vis[i][j]) return; vis[i][j]=true; dfs(board,i-1,j); dfs(board,i+1,j); dfs(board,i,j-1); dfs(board,i,j+1); return; } public: void solve(vector<vector<char>>& board) { if(board.empty()) return; rows=board.size(); cols=board[0].size(); vis.resize(rows,vector<bool>(cols,false)); for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) { if((i==0||i==rows-1||j==0||j==cols-1)&&(board[i][j]=='O')) dfs(board,i,j); } } for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) { if(!vis[i][j]&&board[i][j]=='O') { vis[i][j]=true; board[i][j]='X'; } } } return; } };
Problem solution in C.
void dfs(char **board, int i, int j, int row_sz, int col_sz) { if('X' == board[i][j]) { return; } if('K' == board[i][j]) { return; } board[i][j] = 'K'; if(j-1 > 0) dfs(board, i, j-1, row_sz, col_sz); if(j+1 < col_sz) dfs(board, i, j+1, row_sz, col_sz); if(i-1 > 0) dfs(board, i-1, j, row_sz, col_sz); if(i+1 < row_sz) dfs(board, i+1, j, row_sz, col_sz); } void solve(char** board, int boardSize, int* boardColSize){ if(NULL == board) return; if((boardSize <= 1) || (*boardColSize <= 1)) return; int row_sz = boardSize; int col_sz = *boardColSize; int i,j; for(j=0;j<col_sz;j++) { if(board[0][j] == 'O') dfs(board, 0, j, row_sz, col_sz); } for(i=0;i<row_sz;i++) { if(board[i][col_sz - 1] == 'O') dfs(board, i, col_sz - 1, row_sz, col_sz); } for(j=0;j<col_sz;j++) { if(board[row_sz-1][j] == 'O') dfs(board, row_sz - 1, j, row_sz, col_sz); } for(i=0;i<row_sz;i++) { if(board[i][0] == 'O') dfs(board, i, 0, row_sz, col_sz); } for(i=0;i<row_sz;i++) { for(j=0;j<col_sz;j++) { if(board[i][j] == 'K') board[i][j] = 'O'; else board[i][j] = 'X'; } } }
0 Comments