DFS
# 130. 被围绕的区域 (opens new window)
方法一：DFS
class Solution {
char[][] board;
int m,n;
public void solve(char[][] board) {
this.board = board;
this.m = board.length;
this.n = board[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
// 搜索边界
boolean isEdge = i==0||j==0||i==m-1||j==n-1;
if(isEdge && board[i][j]=='O'){
dfs(i,j);
}
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(board[i][j]=='O'){
board[i][j] = 'X';
}
if(board[i][j]=='#'){
board[i][j] = 'O';
}
}
}
}
// 边界上的O全部标记为#，用于还原
void dfs(int i,int j){
if(i<0||i>=m||j<0||j>=n ||
board[i][j]=='X' ||
board[i][j]=='#'){
return ;
}
board[i][j] = '#';
dfs(i-1,j);
dfs(i+1,j);
dfs(i,j-1);
dfs(i,j+1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
方法二：BFS
class Solution {
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
public void solve(char[][] board) {
int m=board.length,n=board[0].length;
Queue<int[]> que = new LinkedList<>();
for(int i=0;i<m;i++){
if(board[i][0]=='O'){
que.offer(new int[]{i,0});
board[i][0] = '#';
}
if(board[i][n-1]=='O'){
que.offer(new int[]{i,n-1});
board[i][n-1] = '#';
}
}
for(int j=1;j<n-1;j++){
if(board[0][j]=='O'){
que.offer(new int[]{0,j});
board[0][j] = '#';
}
if(board[m-1][j]=='O'){
que.offer(new int[]{m-1,j});
board[m-1][j] = '#';
}
}
while(!que.isEmpty()){
int[] node = que.poll();
int x=node[0],y=node[1];
for(int[] dir:dirs){
int dx=x+dir[0];
int dy=y+dir[1];
if(dx<0||dy<0||dx>=m||dy>=n|| board[dx][dy]!='O'){
continue;
}
que.offer(new int[]{dx,dy});
board[dx][dy] = '#';
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(board[i][j]=='#'){
board[i][j] = 'O';
}else if(board[i][j]=='O'){
board[i][j] = 'X';
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# 200. 岛屿数量 (opens new window)
class Solution {
boolean[][] vis;
char[][] grid;
int m,n;
public int numIslands(char[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
this.vis = new boolean[m][n];
int ret = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='1' && !vis[i][j]){
ret++;
dfs(i,j);
}
}
}
return ret;
}
void dfs(int i,int j){
if(i<0||i>=m||j<0||j>=n||grid[i][j]!='1'){
return ;
}
grid[i][j] = '.';
vis[i][j] = true;
dfs(i+1,j);
dfs(i-1,j);
dfs(i,j-1);
dfs(i,j+1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 463. 岛屿的周长 (opens new window)
class Solution {
int[][] grid;
int m,n;
public int islandPerimeter(int[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1){
return dfs(i,j);
}
}
}
return 0;
}
int dfs(int i,int j){
// 岛->边界 +1
if(i<0||i>=m||j<0||j>=n){
return 1;
}
// 岛->水 +1
if(grid[i][j]==0) return 1;
// 重复走1
if(grid[i][j]!=1) return 0;
// 1->1 将走到的1置2
grid[i][j] = 2;
return dfs(i+1,j)+dfs(i-1,j)+dfs(i,j+1)+dfs(i,j-1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 695. 岛屿的最大面积 (opens new window)
class Solution {
int[][] grid;
int m,n;
public int maxAreaOfIsland(int[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
int ret = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1){
ret = Math.max(ret,dfs(i,j));
}
}
}
return ret;
}
int dfs(int i,int j){
if(i<0||i>=m||j<0||j>=n || grid[i][j]!=1){
return 0;
}
// 置为2 可以表示visited
grid[i][j] = 2;
return dfs(i+1,j)+dfs(i-1,j)+dfs(i,j+1)+dfs(i,j-1)+1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 1020. 飞地的数量 (opens new window)
class Solution {
int[][] grid;
int m,n;
public int numEnclaves(int[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
int ret = 0;
for(int i=0;i<m;i++){
dfs(i,0);
dfs(i,n-1);
}
for(int j=0;j<n;j++){
dfs(0,j);
dfs(m-1,j);
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1){
ret++;
}
}
}
return ret;
}
void dfs(int i,int j){
if(i<0||i>=m||j<0||j>=n||grid[i][j]!=1){
return ;
}
grid[i][j] = 2;
dfs(i+1,j);
dfs(i-1,j);
dfs(i,j+1);
dfs(i,j-1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 1254. 统计封闭岛屿的数目 (opens new window)
class Solution {
int[][] grid;
int m,n;
public int closedIsland(int[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
int ret = 0;
for(int i=0;i<m;i++){
dfs(i,0);
dfs(i,n-1);
}
for(int j=0;j<n;j++){
dfs(0,j);
dfs(m-1,j);
}
for(int i=1;i<m-1;i++){
for(int j=1;j<n-1;j++){
if(grid[i][j]==0){
dfs(i,j);
ret++;
}
}
}
return ret;
}
void dfs(int i,int j){
if(i<0||i>=m||j<0||j>=n || grid[i][j]!=0){
return ;
}
grid[i][j] = 2;
dfs(i+1,j);
dfs(i-1,j);
dfs(i,j+1);
dfs(i,j-1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 365. 水壶问题 (opens new window)
class Solution {
int x;
int y;
int target;
boolean[][] vis;
public boolean canMeasureWater(int x, int y, int target) {
this.x = x;
this.y = y;
this.target = target;
this.vis = new boolean[x+1][y+1];
return dfs(0,0);
}
boolean dfs(int curX,int curY){
if(curX+curY == target)
return true;
if(vis[curX][curY])
return false;
vis[curX][curY] = true;
boolean res1 = dfs(x,curY);
boolean res2 = dfs(curX,y);
// x倒入y中
int yCan = y-curY;
int newCurX = curX-yCan>=0?curX-yCan:0;
int newCurY = curY+curX<=y?curY+curX:y;
boolean res3 = dfs(newCurX,newCurY);
// y倒入x中
int xCan = x-curX;
int newCurX2 = curY+curX<=x?curY+curX:x;
int newCurY2 = curY-xCan>=0?curY-xCan:0;
boolean res4 = dfs(newCurX2,newCurY2);
// 清空
boolean res5 = dfs(0,curY);
boolean res6 = dfs(curX,0);
return res1||res2||res3||res4||res5||res6;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36