# 刷题第5篇：被包围的区域

## 题目描述

https://leetcode-cn.com/problems/surrounded-regions/

```                XXXXXXXXXX                          XXXXXXXXXX
OOOXXXXXOO                          OOOXXXXXOO
XXXXXOOXXX          ----->          XXXXXXXXXX
XXOOXXXXXX                          XXXXXXXXXX
XXXXXOOOOO                          XXXXXOOOOO```

## 解法一：逐个进行DFS

```public void solve(char[][] board) {
int rows = board.length;
if (rows == 0) {
return;
}
int cols = board[0].length;
//考虑除去边界以外的所有 O
for (int i = 1; i < rows - 1; i++) {
for (int j = 1; j < cols - 1; j++) {
if (board[i][j] == 'O') {
//visited 用于记录 DFS 过程中已经访问过的节点
HashSet<String> visited = new HashSet<>();
//如果没有到达边界，就把当前 O 置为 X
if (!solveHelper(i, j, board, visited)) {
board[i][j] = 'X';
}
}
}
}
}

private boolean solveHelper(int row, int col, char[][] board, HashSet<String> visited) {
//是否访问过
if (visited.contains(row + "@" + col)) {
return false;
}

//到达了 X 直接返回 false
if (board[row][col] == 'X') {
return false;
}

if (row == 0 || row == board.length - 1 || col == 0 || col == board[0].length - 1)     {
return true;
}

//分别尝试四个方向
if (solveHelper(row - 1, col, board, visited, memoization)
|| solveHelper(row, col - 1, board, visited, memoization)
|| solveHelper(row + 1, col, board, visited, memoization)
|| solveHelper(row, col + 1, board, visited, memoization)) {
return true;
} else {
return false;
}
}```

## 解法二：由外向内

```public void solve(char[][] board) {
if (board.length < 3 || board[0].length < 3){
return;
}
int[][] direction = {{-1,0},{1,0},{0,1},{0,-1}};
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m ; i++){
for (int  j =0 ; j < n ; j++){
if (board[i][j] == 'O' && T130_isEdge(i,j,board)){//从边界开始向内进行腐蚀
T130(i,j,direction,board);
}
}
}
for (int i = 0; i < m ; i++){
for (int  j =0 ; j < n ; j++){
if (board[i][j] == 'O'){//从边界开始向内进行腐蚀
board[i][j] = 'X';
}else if (board[i][j] == '#'){//将未被包含的字符'O'还原回来
board[i][j] = 'O';
}
}
}
}
public void T130 (int row,int column,int[][] direction,char[][] board ){
if (board[row][column] == '#' || board[row][column] == 'X'){
return;
}
board[row][column] = '#';//使用一个占位符表示未被包围的字符'O'
for (int i = 0 ; i < direction.length ; i++){
//获取新的坐标
int X = row+direction[i][0];
int Y = column+direction[i][1];
if (T130_helper(X,Y,board.length,board[0].length)){//如果新坐标在内部
T130(X,Y,direction,board);
}
}
}
public boolean T130_isEdge(int row,int column,char[][] board){
return row == 0 || column == 0 || row == board.length-1 || column == board[0].length-1;
}
public boolean T130_helper (int X,int Y,int row,int column){
return X >= 0 && X <= row-1 && Y >= 0 && Y <= column-1 ;
}```

## 总结

0 条评论

• ### 回溯：系列经典题目

对于回溯算法，一开始接触感觉还是挺难的，随着刷到的题目的数量增多，慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码

• ### 剑指offer第11题：机器人运动范围

此方法我们可以直接按照题目中的要求，将所有的方格全都访问一遍，由于所有的格子需要满足一个条件，连续性和单元格的坐标和小于n即可。

• ### 剑指offer第10题：矩阵中的路径

根据题目要求，需要我们从一个已知矩阵中找到一个可以挨个形成给定字符串的路径。如果有这条路径的话，我们需要返回true，如果没有的话，我们返回false，并且相同...

• ### 基于一维级联快速膨胀与腐蚀算法

一：基本原理 膨胀与腐蚀是图像形态学两个基本操作之一，传统的代码实现都是基于二维窗口卷积模式，对于正常的3x3窗口要八次与运算，而基于一维级联方式先X方向后Y方...

• ### OpenCV 学习日记（三）--- 常见数据类型

OpenCV基本数据类型： CvPoint，这些结构中最简单的一个，包含两个整型变量x和y。 CvPoint还有两个兄弟：CvPoint2D32f 和 CvPo...

• ### 华为突破封锁，对标谷歌Dropout专利，开源自研算法Disout，多项任务表现更佳

美国持续封锁，华为的技术自研，已经深入到了AI底层算法层面上，并开始将研究成果面向业界开源。

• ### poj 1316 Self Numbers

题意：找出10000以内所有的不能由n+n的各位数字和组成的数字 #include<stdio.h> #include<string.h> int main()...

• ### C++版 - Leetcode 69. Sqrt(x) 解题报告【C库函数sqrt(x)模拟-求平方根】

Total Accepted: 93296 Total Submissions: 368340 Difficulty: Medium

• ### 零售业数据分析那些事儿

随着大数据时代的到来，数据分析已经成为了零售业非常重要的一环，也是精细化运营的基础。零售业数据分析包括：