算法(28)--矩阵搜索系列

1.leetcode-200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

class Solution(object):
    def numIslands(self, grid):
        def dfs(r,c):
            grid[r][c]="0"
            for i,j in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
                if 0<=i<m and 0<=j<n and grid[i][j]=="1":
                    # print(i,j)
                    dfs(i,j)
        count=0
        m=len(grid)
        if m==0:
            return count
        n=len(grid[0])
        for r in range(m):
            for c in range(n):
                if  grid[r][c]=="1":
                    count+=1
                    dfs(r,c)
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.leetcode-695. 岛屿的最大面积

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

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

class Solution(object):
    def __init__(self):
        self.count=0
    def maxAreaOfIsland(self, grid):
        def dfs(r,c):
            grid[r][c]=0 
            self.count+=1
            for i,j in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
                if 0<=i<m and 0<=j<n and grid[i][j]==1:
                    dfs(i,j)
        res=0
        m=len(grid)
        if m==0:
            return res
        n=len(grid[0])
        for r in range(m):
            for c in range(n):
                if grid[r][c]==1:
                    self.count=0
                    dfs(r,c)
                res=max(res,self.count)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.leetcode-463. 岛屿的周长

给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

只有一个岛屿
从陆地走向边界/水域，边长+1。判断下一个坐标是边界位置还是水域，从而改变总周长。

class Solution(object):
    def __init__(self):
        self.res = 0
    def islandPerimeter(self, grid):
        def dfs(i,j):
            # print(i,j, self.res)
            grid[i][j] = 2
            for r, c in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:  # 走四个方向，看会发生什么情况嘛
                if r < 0 or r >= m or c < 0 or c >= n:     # 往边界走了一格,
                    # print("bian",i,j,r,c)
                    self.res += 1
                if 0<= r < m and 0<= c < n and grid[r][c] == 0 : # 往水域走了一格
                    # print("shui",i,j,r,c)
                    self.res +=1
                if 0<= r < m and 0<= c < n and grid[r][c] == 1:   
                    dfs(r,c)
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        for i in range(m):   # 要区别是走过的陆地不能走还是原本就是水域不能走
            for j in range(n):
                # print(i,j)
                if grid[i][j] == 1:
                    dfs(i,j)
        return self.res

grid=[[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
so = Solution()
print(so.islandPerimeter(grid))
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

4.剑指 Offer 12. 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

约束：不能两次经过同一个点
矩阵中的每一个元素，dfs + visted矩阵，上下左右匹配当前字符，
visted矩阵通过标记字符来实现

递归前保证矩阵下标的合理性，递归出口由匹配情况控制
1.word==""
2.len(word) == 1 and board[i][j] == word[0]
3.board[i][j] != word[0]
其他情况都是往下递归

class Solution(object):
    def exist(self, board, word):
        # board[i][j] 都进行深度优先匹配
        def dfs(i,j,word):
            if len(word) == 0:    # word 为空字符串时,匹配完成
                return True
            if len(word) == 1 and board[i][j] == word[0]:  # 防止[i][j]下一步都是边界且是访问过的情况，虽然已经匹配，但是结果是false，[["a"]]"a"
                return True
            if board[i][j] != word[0]: # 第一字符不匹配，完全不用递归，直接输出
                return False
            tmp = board[i][j]                           # 完全没有考虑不能重复走 
            board[i][j] = None
            for r,c in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]: # 第一哥字符匹配，递归处理
                if 0<= r < m and 0 <= c < n:
                    if dfs(r,c,word[1:]):  # 如果四个方向中有一格方向是可行的就返回True       
                        return True
            board[i][j] = tmp
            return False                # 第一个字符匹配了，但是后面的都不配，输出False
            

        m = len(board)
        if m == 0:
            return word == "" 
        n = len(board[0])
        for i in range(m):
            for j in range(n):
                if dfs(i,j,word):
                    return True
        return False  # 所有遍历过了，没有就输出false

#[["a"]],"a"
#[["a"]],"a"
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

5.leetcode-329. 矩阵中的最长递增路径

给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。
1
2
3
4
5
6
7
8

keypoint:
1.递增天然的不会两次走过同一个单元
2.dp[i][j] 以matrix[i][j]开始的最长递增路径

class Solution(object):
    def longestIncreasingPath_cyy(self, matrix):
        def dfs(i,j):
            if dp[i][j]:
                return dp[i][j]
            for r, c in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                if 0<= r < m and 0 <= c < n  and matrix[r][c] > matrix[i][j]:
                    dp[i][j] = max(dp[i][j], dfs(r,c))  # 下一层的最大深度
            dp[i][j] += 1  # 本层的深度在下层深度的基础上+1
            return dp[i][j]
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        dp = [[0] * n for _ in range(m)]  # dp[i][j] 开始的最长路径
        res = 0
        for i in range(m):
            for j in range(n):
                res = max(res,dfs(i,j))
        # print(dp)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

6.leetcode-1091. 二进制矩阵中的最短路径

在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。

一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, …, C_k 组成：

相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
C_1 位于 (0, 0)（即，值为 grid[0][0]）
C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。

最短路径问题：BFS

def shortestPathBinaryMatrix(self, grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[-1][-1] == 1:
        return -1
    if n == 1:                # [[0]]这种特殊情况
        return 1
    res = 1
    que = [(0,0)]
    while(que):
        l = len(que)
        for i in range(l):
            (i,j) = que.pop(0)
            for (r,c) in [(i-1,j-1),(i-1,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1)]:
                if 0<= r < n and 0<= c < n and grid[r][c] == 0: # 有效坐标 并且能走
                    if r == n-1 and c == n-1:        # 能走到了终点
                        return res + 1
                    que.append((r,c))                # 能走没到终点
                    grid[r][c] = 1                   # 已经走过的地方不能再走，不然就会一直进队出队
        res += 1                                     # 广度优先的层数
    return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20