二维数组的深度优先搜索总结以及模板(一) LeetCode 200 Number of Islands(二) LeetCode 695. Max Area of Island(三)1020. Number of Enclaves(四)1254. Number of Closed Islands(五)130. Surrounded Regions六：剑指offer : 矩阵中的路径七：剑指offer :机器人的运动范围

(一) LeetCode 200 Number of Islands

1.题意

给定一个二维矩阵，只包含0,1，所有相连的1被认为是一座岛屿，求总共的岛屿数量

2.示例

3.解题思路及代码实现

计算二维数组中的连通个数，连通是指可以从一个点经过上下左右四个方向可以到达。
此时就是通过深度优先搜索来遍历数组。

DFS实现的java代码如下所示：以下几乎为二维数组的深度优先遍历的模板~

class Solution {
    private int[][] directions = {{1,-1,0,0},{0,0,1,-1}}; //上下左右四个方向的坐标变化
    
    public int numIslands(char[][] grid) {
        if(grid==null || grid.length==0) return 0;
        int ans = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length]; // 记录每一点是否被访问过
        for(int i=0;i<grid.length;i++){ //调用一次函数dfs(),就搜索完一个连通区域，此时ans+1
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1' && visited[i][j]==false) 
                    ans+=dfs(grid,visited,i,j);
            }
        }
        return ans;
    }
    
    public int dfs(char[][] grid,boolean[][] visited,int x,int y)
    {
        if(x<0 || x>=grid.length || y<0 || y>=grid[0].length ) //不能越界
            return 0;
        visited[x][y]=true;
        for(int i=0;i<4;i++){  //对于当前坐标点(x,y)，再对它的四个方向进行遍历
            int xx = x+directions[0][i];
            int yy = y+directions[1][i];
            if(xx>=0 && xx<grid.length && yy>=0 && yy<grid[0].length && visited[xx][yy]==false && grid[xx][yy]=='1'){
                visited[xx][yy] = true;
                dfs(grid,visited,xx,yy);
            }  
        }
        return 1;
    }
}

避免重复访问的一种方法是：
一是用set()记录一下访问过的点,这样不修改输入数组。
二是直接修改grid数组，访问这个点后修改为一个特殊值。
python 实现：

class Solution(object):
    def numIslands(self, grid):
        
        def dfs(grid, i, j):
            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y] == '1' and (x,y) not in vis:
                    vis.add((x,y))
                    dfs(grid, x, y)
                   
        if not grid or not grid[0]: return 0
        res = 0
        vis = set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1' and (i,j) not in vis:
                    vis.add((i,j))
                    dfs(grid, i, j)
                    res += 1
        return res

(二) LeetCode 695. Max Area of Island

1.题意

给定一个包含了一些 0 和 1的二维数组 grid[][] , 一个岛屿是由四个方向 (水平或垂直) 的 1 构成。你可以假设二维矩阵的四个边缘之外都被水包围着。
找到给定的二维数组中最大的岛屿面积，及找二维数组中的最大连通区域的大小。
(如果没有岛屿，则返回面积为0)

2.示例

输入：
11000
11000
00100
00011

输出：4

最大的岛屿就是前两行的4个1组成的岛屿。

3.解题思路及代码实现

只需要在一次深度优先搜索时把一次搜索到的所有连通的1加起来，就是一个连通区域的岛屿数，最后比较一下每一次调用函数dfs()所返回的岛屿数，把最大的岛屿数返回。

DFS实现的java代码如下所示：

public class Max_Area_Island_695 {
    int[][] direction = {{1,0,-1,0},{0,1,0,-1}}; //四个方向
    
    public int maxAreaOfIsland(int[][] grid) {
        if(grid==null || grid.length==0) return 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int Max = 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1 && visited[i][j]==false){ 
                    int res=dfs(grid,visited,i,j);
//                    System.out.println(res);
                    if(res>Max)  Max = res;
                }
            }
        }
        return Max;
    }

    public int dfs(int[][] grid,boolean[][] visited,int x,int y){
        if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y]==0)
            return 0;
        int res = 1; //这个节点的grid[x][y]==1,岛屿的个数至少为1
        visited[x][y]=true;
//        System.out.println(x+" "+y);
        for(int i=0;i<4;i++){
                int xx = x+direction[0][i];
                int yy = y+direction[1][i];
                if(xx>=0 && xx<grid.length && yy>=0 && yy<grid[0].length && visited[xx][yy]==false && grid[xx][yy]==1){
                    visited[xx][yy]=true;
                    res+=dfs(grid,visited,xx,yy);
                }
        }
        return res;    
    }     
}

python实现：

(三)1020. Number of Enclaves

1.题意

给定一个二维矩阵，只包含0,1，所有相连的1被认为是一个岛屿，人可以在岛屿上行走。认为矩阵外是危险的，能走到矩阵外的岛屿也是危险的，求矩阵中不危险的岛屿的面积。

2.示例

输入：

输出： 3

3.解题思路及代码实现

从边界的1开始深搜，把与边界1相连的所有点都找出来，然后统计出所有为1的个数，两者相减就是最终的结果。

class Solution(object):
    def numEnclaves(self, A):   
        cnt = 0 # 统计1的个数
        vis = set()
        m, n = len(A), len(A[0])
        def dfs(i,j):
            for (x,y) in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                if 0<=x<m and 0<=y<n and A[x][y]==1 and (x,y) not in vis:
                    vis.add((x,y))
                    dfs(x,y)
        
        for i in range(m):
            for j in range(n):
                if A[i][j] == 1:
                    cnt += 1 # 统计所以值为1的点的个数
                    if i == 0 or i == m-1 or j == 0 or j == n-1: # 到达边界后再统计与边界相连的值为1的点的个数
                        dfs(i, j)
                        vis.add((i,j)) # 把与边界为1的点和相连的点都存在vis中
        return cnt - len(vis)

(四)1254. Number of Closed Islands

1.题意

给定一个二维数组，其中0代表岛屿，1代表水，找出封闭的岛屿的个数！！
封闭的意思是岛屿的四周全是水。

3.解题思路及代码实现

和和LeetCode 1020 number of enclaves 类似

• 首先，从边界上的岛屿出发，把与边界相连接的岛屿都去掉
• 然后，遍历内部的岛屿，遇到一个岛屿就把与它相连的岛屿都去掉，此时找到一个封闭的岛屿

特别注意： 当到dfs()函数中时，默认(i,j)已经被访问过了，dfs(i,j)遍历的是(i,j)上下左右四个邻居，而不包括当前(i,j)这个点！

class Solution(object):
    def closedIsland(self, grid):
        m, n = len(grid), len(grid[0])
        def dfs(i, j):
            for (x,y) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:  # 上下左右
                if 0<=x<m and 0<=y<n and grid[x][y]==0:
                    grid[x][y] = 1
                    dfs(x,y)
        
        for i in range(m):
            for j in range(n):
                if (i==0 or i==m-1 or j==0 or j==n-1) and grid[i][j]==0: # 去掉边界相连的岛屿
                    grid[i][j] = 1
                    dfs(i, j)
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==0:  # 遇到一个岛屿，然后把与这个岛屿相连接的岛屿都去掉
                    res += 1
                    grid[i][j] = 1
                    dfs(i, j)
        
        return res

(五)130. Surrounded Regions

1.题意

一个二维数组，由"X"和"O"组成，把数组内部的"O"反转为"X"，但是边界上的"O"和与边界"O"相连的那些点不用反转

2.示例

输入：
X X X X
X O O X
X X O X
X O X X
输出：
X X X X
X X X X
X X X X
X O X X

3.解题思路及代码实现

和LeetCode 1020 number of enclaves 类似

首先把边界上为"O"的点找出来，然后对这个点进行dfs()操作，把与边界为"O"的点相连的点都找出来，存储在vis中，然后把不在vis中的"O"反转为"X"就行。

class Solution(object):
    def solve(self, board):
   
        if not board or not board[0]: return board
        
        m, n = len(board), len(board[0])
        
        vis = set() # 记录边界为O的点和与之相连的点的坐标
        
        def dfs(i, j):
            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]: # 把与边界相连的点都找出来存在vis中
                if 0<=x<m and 0<=y<n and board[x][y] == 'O' and (x, y) not in vis:
                    vis.add((x,y))
                    dfs(x,y)
                
        for i in range(m):
            if board[i][0] == 'O': # 第一列
                vis.add((i,0))
                dfs(i,0)
            if board[i][n-1] == 'O': # 最后一列
                vis.add((i,n-1))
                dfs(i,n-1)
                
        for j in range(n):
                if board[0][j] == 'O': # 第一行
                    vis.add((0,j))
                    dfs(0, j)
                if board[m-1][j] == 'O': #最后一行
                    vis.add((m-1, j))
                    dfs(m-1, j)
        # 反转'O'为'X'
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O' and (i,j) not in vis:
                    board[i][j] = 'X'

六：剑指offer : 矩阵中的路径

题意：

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

最恶心的就是用例给的是矩阵，但是函数中的matrix是一维数组，我没注意导致一直越界

python 实现: DFS + 回溯（好好理解，很重要）

# -*- coding:utf-8 -*-
# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        if not matrix and not path: return True
        if not matrix and path: return False
        if not path: return False
        
        vis = set()
        for i in range(rows): # j是行啊
            for j in range(cols): # i是列
                if self.dfs(matrix, rows, cols, path, i, j, 0, vis):
                    return True
        return False
    
    def dfs(self, matrix, rows, cols, path, row, col, idx, vis):
            if row < 0 or row >= rows or col < 0 or col >= cols or (row, col) in vis or matrix[col + row * cols] != path[idx]:
                return False
            if idx == len(path)-1: 
                return True
            vis.add((row, col))
            for (x, y) in [(row+1, col), (row-1, col), (row, col+1), (row, col-1)]:
                if self.dfs(matrix, rows, cols, path, x, y, idx+1, vis):
                    return True
            vis.remove((row, col))  # 为False才会到这来，说明这个点访问了没用，回溯一下
            return False

七：剑指offer :机器人的运动范围

题意：

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路：

刚开始想错了，题意是从（0,0）出发能到达的节点中，满足行坐标和列坐标的数位之和小于等于k的格子都可以，求出总个数。
可以使用深度优先搜索，也可以使用广度优先搜索，还可以使用回溯法来做啊！

方法一：BFS

很容易理解，只要定义好起始节点和下一层节点就行，然后不断遍历每一层的节点。

class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        if threshold <=0 or rows <= 0 or cols <= 0: return 0
        
        return self.bfs(threshold, rows, cols)
    
    def bfs(self, threshold, rows, cols): # 矩阵维度
            ret = 1
            queue = [(0, 0)]  # 起始点
            vis = set()
            vis.add((0,0))
            while queue:
                i, j = queue.pop()
                for (x, y) in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                    if x < 0 or x >= rows or y < 0 or y >= cols or (x, y) in vis: 
                        continue
                    
                    vis.add((x, y))
                    if self.check(threshold, x, y):
                        queue = [(x, y)] + queue  # bfs
                        ret += 1
            return ret
                        
    def check(self, threshold, row, col):
        res = 0
        while row:
            res += (row % 10)
            row /= 10
        
        while col:
            res += (col % 10)
            col /= 10
        if res > threshold: 
            return False
        return True

方法二：DFS

经典的二维数组的深度优先搜索，也很好写啊！
定义好起始节点，然后从这个结点开始搜索啊！

class Solution:
    def __init__(self):
        self.res = 0
    
    def movingCount(self, threshold, rows, cols):
        # write code here
        if threshold < 0 or rows <= 0 or cols <= 0: return 0
        vis = set()
        self.dfs(threshold, rows, cols, vis, 0, 0)
        return self.res
    
    def dfs(self, threshold, rows, cols, vis, i, j): # 从点（i, j）进行搜索啊
            if i < 0 or i >= rows or j < 0 or j >= cols or (i, j) in vis: 
                return
            if not self.check(threshold, i, j):
                return
            vis.add((i, j))
            self.res += 1
            for (x, y) in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                self.dfs(threshold, rows, cols, vis, x, y)
                
            
    def check(self, threshold, row, col):
        res = 0
        while row:
            res += (row % 10)
            row /= 10
        
        while col:
            res += (col % 10)
            col /= 10
        if res > threshold: 
            return False
        return True

最后

以上就是高高缘分为你收集整理的二维数组的深度优先搜索总结以及模板(一) LeetCode 200 Number of Islands(二) LeetCode 695. Max Area of Island(三)1020. Number of Enclaves(四)1254. Number of Closed Islands(五)130. Surrounded Regions六：剑指offer : 矩阵中的路径七：剑指offer :机器人的运动范围的全部内容，希望文章能够帮你解决二维数组的深度优先搜索总结以及模板(一) LeetCode 200 Number of Islands(二) LeetCode 695. Max Area of Island(三)1020. Number of Enclaves(四)1254. Number of Closed Islands(五)130. Surrounded Regions六：剑指offer : 矩阵中的路径七：剑指offer :机器人的运动范围所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。