二维矩阵DFS

发表于 | 分类于 ，

题目：输出所有路径数

题目描述

思路：DFS

  从起点开始，DFS，直到走到终点，用一个全局变量res[0]记录所有路径数量。

代码:

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
##dirs为上下左右方向
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
##结果设为全局变量
res = 0
##原始矩阵
graph = [[0, 1, 0, 0, 0], [0, 2, 3, 0, 0], [0, 0, 4, 5, 0], [0, 0, 7, 6, 0]]
row = 4
col = 5
##起始点和终点
x1, y1, x2, y2 = 0, 1, 3, 2

def dfs(x1, y1, visited):
	global res
    if x1 == x2 and y1 == y2:
        res += 1
        return
    for i, j in dirs:
        tmp_x = i + x1
        tmp_y = j + y1
        if 0 <= tmp_x < row and 0 <= tmp_y < col and graph[tmp_x][tmp_y] > graph[x1][y1] \
                and (tmp_x, tmp_y) not in visited:
            dfs(tmp_x, tmp_y, visited | {(tmp_x, tmp_y)})

dfs(x1, y1, {(x1, y1)})
print(res)

题目：图像渲染

题目描述

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

1
2
3
4
5
6
7
8
9
输入: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

思路：DFS

​ 边界：如果当前值被浏览过则停止。即被赋予过新值。

​ 递归子问题：从起点开始，将当前点赋值为新值，上下左右移动查看符合条件（值与起始点相同，在矩阵维度内）的位置点，进行DFS。

代码

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
def floodFill(self, image, sr, sc, newColor):
    """
    :type image: List[List[int]]
    :type sr: int
    :type sc: int
    :type newColor: int
    :rtype: List[List[int]]
    """
    ##上下左右移动方向
    stack = [(-1,0),(1,0),(0,-1),(0,1)] 
    ##矩阵维度
    self.m , self.n = len(image) , len(image[0])
    ##val表示起点值
    self.val = image[sr][sc] 
    ##递归函数
    def dfs(image,x,y,newColor):
        ##如果该值被浏览过，则退出（边界）
        if image[x][y] == newColor:
            return image
        ##将当前位置赋值为新值
        image[x][y] = newColor
        for i,j in stack:
            ##tmpx,tmpy是上下左右移动的值
            tmpx = x + i
            tmpy = y + j
            ##如果tmpx,tmpy在矩阵维度范围内，且该位置的值和起始点值一样，则进入递归。
            if 0 <= tmpx < self.m and 0 <= tmpy < self.n and image[tmpx][tmpy] == self.val:
                dfs(image,tmpx,tmpy,newColor)
    if 0 <= sr < self.m and 0 <= sc < self.n:
        dfs(image,sr,sc,newColor)
    return image

题目：单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

1
2
3
4
5
6
7
8
9
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

思路：DFS

对所有的点进行遍历，找到第一个字母与word的第一个字母相同的，开始进行dfs。

代码

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
class Solution:
    def exist(self, board,word):
        if not word:
            return True
        if not board or not board[0]:
            return False
        self.m , self.n = len(board) , len(board[0])
        stack = [(0,1),(0,-1),(1,0),(-1,0)]
        self.flag = False
        ##DFS
        def dfs(board,word,stack,x,y,w,visited):
            if w == len(word):
                self.flag = True
                return 
            for i,j in stack:
                temx = x + i
                temy = y + j
                if 0 <= temx < self.m and 0 <= temy < self.n and board[temx][temy] == word[w] and (temx,temy) not in visited:
                    dfs(board,word,stack,temx,temy,w+1,visited|{(temx,temy)})
                    ##这里是要一遇到可不继续递归则立马停止，不然时间复杂度太高
                    if self.flag:
                        return
        #每个点都有看是不是可以作为起始。
        for i in range(self.m):
            for j in range(self.n):
                if board[i][j] == word[0]:
                    dfs(board,word,stack,i,j,1,{(i,j)})
                    ##这里是要一遇到可不继续递归则立马停止，不然时间复杂度太高
                    if self.flag:
                        return True
        return self.flag

题目：岛屿的最大面积

题目描述

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

1
2
3
4
5
6
7
8
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

1
[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

思路：DFS

  遍历矩阵，遇到 grid [i] [j] = 1时，就算值【采用dfs来算】

  dfs : 先将grid [i] [j] 置0，然后再 return 1 + 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
def maxAreaOfIsland(self, grid):
       """
       :type grid: List[List[int]]
       :rtype: int
       """
       if not grid:
           return 0
       l,h = len(grid),len(grid[0])
       
       def dfs(i,j):
           if 0 <= i < l and 0 <= j < h and grid[i][j]:
               grid[i][j] = 0
               return 1 + dfs(i-1,j) + dfs(i+1,j) +dfs(i,j-1) + dfs(i,j+1)
           return 0
           
       result = [dfs(i,j) for i in range(l) for j in range(h) if grid[i][j]]
       return max(result) if result else 0

题目：岛屿的个数

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3

思路：DFS

​ 遍历矩阵，遇到 grid [i] [j] = 1时，将最大面积的岛屿置0【采用dfs来算】，res记录几个岛屿个数。

  dfs : 将grid [i] [j] 置0

代码

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
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0
        stack = [(-1,0),(1,0),(0,1),(0,-1)]
        self.m , self.n = len(grid) , len(grid[0])
        res = 0
        def dfs(grid,stack,x,y):
            grid[x][y] = '0'
            for i,j in stack:
                tmpx = x + i
                tmpy = y + j
                if 0 <= tmpx < self.m and 0 <= tmpy < self.n and grid[tmpx][tmpy] == '1':
                    dfs(grid,stack,tmpx,tmpy)
            return grid
        for i in range(self.m):
            for j in range(self.n):
                if grid[i][j]=='1':
                    dfs(grid,stack,i,j)
                    res += 1
        return res

题目：最大正方形

题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

1
2
3
4
5
6
输入: 
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

思路：动态规划

img

代码

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
public class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[m][n];
        // 第一列赋值
        for(int i = 0; i < m; i++){
            dp[i][0] = matrix[i][0] - '0';
            max = Math.max(max, dp[i][0]);
        }
        // 第一行赋值
        for(int i = 0; i < n; i++){
            dp[0][i] = matrix[0][i] - '0';
            max = Math.max(max, dp[0][i]);
        }
        // 递推
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = matrix[i][j] == '1' ? Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1 : 0;
                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }
}

题目：01矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:
输入:

1
2
3
0 0 0
0 1 0
0 0 0

输出：

1
2
3
0 0 0
0 1 0
0 0 0

示例 2:
输入:

1
2
3
0 0 0
0 1 0
1 1 1

输出:

1
2
3
0 0 0
0 1 0
1 2 1

注意:

  1. 给定矩阵的元素个数不超过 10000。
  2. 给定矩阵中至少有一个元素是 0。
  3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

思路1：DFS

代码

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
class Solution {
public:
    int dfs(vector<vector<int>> &matrix,int i,int j,int R,int C,bool** visited){
        int res=R+C;

        if (0==matrix[i][j]) return 0;

        visited[i][j]=true;

        if (j>0&&!visited[i][j-1]){//left
            res=min(res,1+dfs(matrix,i,j-1,R,C,visited));
        }
        if (j<C-1&&!visited[i][j+1]){//right
            res=min(res,1+dfs(matrix,i,j+1,R,C,visited));
        }
        if (i>0&&!visited[i-1][j]){//up
            res=min(res,1+dfs(matrix,i-1,j,R,C,visited));
        }
        if (i<R-1&&!visited[i+1][j]){//down
             res=min(res,1+dfs(matrix,i+1,j,R,C,visited));
        }

        visited[i][j]=false;

        return res;
    }

    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int R=matrix.size(),C=matrix[0].size();
        vector<vector<int>> ret(R,vector<int>(C,0));

        bool **visited=new bool *[R];
        for (int i=0;i<R;i++){
           visited[i]=new bool [C];
           fill(visited[i],visited[i]+C,false);
        }

        for (int i=0;i<R;i++){
            for (int j=0;j<C;j++){
                ret[i][j]=dfs(matrix,i,j,R,C,visited);
            }
        }
        delete [] visited;
        return ret;
    }
};

思路2：BFS

题目：被围绕的区域

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

1
2
3
4
X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

1
2
3
4
X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

思路：DFS

题意就是找出被‘X’完全包围的‘O’的区域，填充为‘X’。

解决思路就是反向找出没有完全被‘X’完全包围的‘O’的区域，标记一下，然后没有标记的就是要被填充的。

  • 思路就是绕着矩阵的最外圈转一圈，碰到‘O’，说明这里可以往里进行深搜；
  • 将深搜经过的所有‘O’都标记成‘Y’；
  • 外圈深搜完成后，所有没有被包围的‘O’都已经标记成了‘Y’；
  • 将所有‘Y’填充为‘O’，所有‘O’填充为‘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
def solve(board):
    """
    Do not return anything, modify board in-place instead.
    """
    if not board or not board[0]:
        return
    m , n = len(board) , len(board[0])
    stack = [(0,1),(0,-1),(1,0),(-1,0)]
    #将深搜经过的所有‘O’都标记成‘Y’；
    def dfs(board,x,y,stack,m,n):
        board[x][y] = 'Y'
        for i,j in stack:
            temx = x + i
            temy = y + j
            if 0 <= temx < m and 0 <= temy < n and board[temx][temy] == 'O':
                board[temx][temy] = 'Y'
                dfs(board,temx,temy,stack,m,n)
    #外圈深搜完成后，所有没有被包围的‘O’都已经标记成了‘Y’；
    for y in range(n):
        if board[0][y] == 'O':
            dfs(board,0,y,stack,m,n)
    for x in range(m):
        if board[x][n-1] == 'O':
            dfs(board,x,n-1,stack,m,n)            
    for y in range(n):
        if board[m-1][y] == 'O':
            dfs(board,m-1,y,stack,m,n)
    for x in range(m):
        if board[x][0] == 'O':
            dfs(board,x,0,stack,m,n)
    #将所有‘Y’填充为‘O’，所有‘O’填充为‘X’。
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == 'Y':
                board[i][j] = 'O'