力扣面试150题--被围绕的区域

Day 60

题目描述

思路

中译中 此题的目的在于找到被X包围的O,没有被完全包围（指与边缘的O相连）不算，将完全包围的O变成X
做法：根据以上中译中，我们可以逆向思维，从边缘的O开始找到与其相连的O,这种岛屿是不需要修改为X,我们将其修改为1，在最后再统一处理，将1改为O,将O改为X。
具体找到i相连的岛屿，可以通过深度搜索实现。

class Solution {public void dfs(char[][]board,int i,int j){if(i>=board.length||i<0||j<0||j>=board[0].length||board[i][j]!='O'){//超出边缘或者不为0就返回return;}//边缘为0board[i][j]='1';dfs(board,i-1,j);dfs(board,i+1,j);dfs(board,i,j-1);dfs(board,i,j+1);}public void solve(char[][] board) {//换个思路，只要和边缘的O相连的都是不该被改成X的点for(int j=0;j<board[0].length;j++){//第一行和最后一行dfs(board,0,j);dfs(board,board.length-1,j);}for(int i=0;i<board.length;i++){//第一列和最后一列dfs(board,i,0);dfs(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]=='1'){board[i][j]='O';}else if(board[i][j]=='O'){board[i][j]='X';}else{board[i][j]=board[i][j];}}}return;}
}