LeetCode-130. 被围绕的区域

• 题目描述
• 解题思路
• 深度优先算法
• 广度优先算法

题目描述

给你一个 m x n 的矩阵 board ，由若干字符 X 和 O ，找到所有被 X 围绕的区域，并将这些区域里所有的 O用 X 填充。

注意边界上的O不会被包围，也就是边界上的O不会被填充成为X

解题思路

board 矩阵中具有三种元素，字符X，被X包围的字符O，没有被X包围的字符O

由于边界上的O不会被填充为X，所以可以转换思想为所有不被X包围的O都与边界的O直接或者间接的相连。

访问四边的边界开始，边界的O就是起点，将O和直接或者间接相连的O标记起来。

标记设定为字符 A，数组标记完毕之后，遍历数组，被标记的就是O没有被标记的就是X

深度优先算法

DFS，从边界开始遍历递归遍历数组进行标记，这里在标记左右和上下两组边的时候，去掉重叠的部分，dfs中判断直接或者间接与边界O相邻的情况就标记为A，这样标记结束之后，数组就剩下标记的A和未标记的O以及原来的X，未标记的O就是被包围的，将其更新为X，标记的A就是未被包围的字符，将其更新为O

dfs 控制边界一旦越界就结束

class Solution {int row,col;public void solve(char[][] board) {row = board.length;if(row == 0) return;col = board[0].length;// 初始化board左右两个边,0和col-1列for(int i = 0; i < row; i++){dfs(board,i,0);dfs(board,i,col - 1);}// 初始化board上下两个边，不包含重叠的部分for(int j = 1; j < col-1; j++){dfs(board,0,j);dfs(board,row-1,j);}// 根据标记还原数组for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(board[i][j] == 'A'){board[i][j] = 'O';}else if(board[i][j] == 'O'){board[i][j] = 'X';}}}}public void dfs(char[][] board,int i,int j){if(i < 0 || i >= row || j < 0 || j >= col || board[i][j] != 'O'){return;}// 直接或者间接与边界O相连board[i][j] = 'A';dfs(board,i+1,j);dfs(board,i-1,j);dfs(board,i,j+1);dfs(board,i,j-1);}
}

广度优先算法

左边和右边的初始化，遇到O入队并且标记

初始化了方向数组，遍历一次对应上下左右的直接相邻。使用了队列保存边界O的联通元素的索引，队列具有O的连通分量就是入队，将该位置标记为A

最后将标记的位置的元素还原即可

class Solution {public void solve(char[][] board) {int row = board.length;if(row == 0) return;int col = board[0].length;int[] dx = {1,-1,0,0};int[] dy = {0,0,1,-1};Deque queue = new LinkedList<>();// 初始化并且标记四个边for(int i = 0; i < row; i++){if(board[i][0] == 'O'){queue.offer(new int[]{i, 0});board[i][0] = 'A';}if(board[i][col-1] == 'O'){queue.offer(new int[]{i, col-1});board[i][col-1] = 'A';}}for(int i = 1; i < col-1; i++){if(board[0][i] == 'O'){queue.offer(new int[]{0, i});board[0][i] = 'A';}if(board[row-1][i] == 'O'){queue.offer(new int[]{row-1, i});board[row-1][i] = 'A';}}while(!queue.isEmpty()){int[] e = queue.poll();int x = e[0],y = e[1];for(int i = 0; i < 4; i++){int mx = x + dx[i],my = y + dy[i];if(mx < 0 || mx >= row || my < 0 || my >= col || board[mx][my] != 'O'){continue;}queue.offer(new int[]{mx,my});board[mx][my] = 'A';}}for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(board[i][j] == 'A'){board[i][j] = 'O';}else if(board[i][j] == 'O'){board[i][j] = 'X';}}}}
}