矩陣搜索

• 1.leetcode-200. 島嶼數(shù)量
• 2.leetcode-695. 島嶼的最大面積
• 3.leetcode-463. 島嶼的周長
• 4.劍指 Offer 12. 矩陣中的路徑
• 5.leetcode-329. 矩陣中的最長遞增路徑
• 6.leetcode-1091. 二進制矩陣中的最短路徑

1.leetcode-200. 島嶼數(shù)量

給你一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網(wǎng)格，請你計算網(wǎng)格中島嶼的數(shù)量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向或豎直方向上相鄰的陸地連接形成。

此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。

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=0m=len(grid)if m==0:return countn=len(grid[0])for r in range(m):for c in range(n):if grid[r][c]=="1":count+=1dfs(r,c)return count

2.leetcode-695. 島嶼的最大面積

給定一個包含了一些 0 和 1 的非空二維數(shù)組 grid 。

一個 島嶼 是由一些相鄰的 1 (代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個 1 必須在水平或者豎直方向上相鄰。你可以假設(shè) grid 的四個邊緣都被 0（代表水）包圍著。

找到給定的二維數(shù)組中最大的島嶼面積。(如果沒有島嶼，則返回面積為 0 。)

class Solution(object):def __init__(self):self.count=0def maxAreaOfIsland(self, grid):def dfs(r,c):grid[r][c]=0 self.count+=1for 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=0m=len(grid)if m==0:return resn=len(grid[0])for r in range(m):for c in range(n):if grid[r][c]==1:self.count=0dfs(r,c)res=max(res,self.count)return res

3.leetcode-463. 島嶼的周長

給定一個包含 0 和 1 的二維網(wǎng)格地圖，其中 1 表示陸地 0 表示水域。
網(wǎng)格中的格子水平和垂直方向相連（對角線方向不相連）。整個網(wǎng)格被水完全包圍，但其中恰好有一個島嶼（或者說，一個或多個表示陸地的格子相連組成的島嶼）。

島嶼中沒有“湖”（“湖” 指水域在島嶼內(nèi)部且不和島嶼周圍的水相連）。格子是邊長為 1 的正方形。網(wǎng)格為長方形，且寬度和高度均不超過 100 。計算這個島嶼的周長。

只有一個島嶼
從陸地走向邊界/水域，邊長+1。判斷下一個坐標是邊界位置還是水域，從而改變總周長。

class Solution(object):def __init__(self):self.res = 0def islandPerimeter(self, grid):def dfs(i,j):# print(i,j, self.res)grid[i][j] = 2for r, c in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]: # 走四個方向，看會發(fā)生什么情況嘛if r < 0 or r >= m or c < 0 or c >= n: # 往邊界走了一格,# print("bian",i,j,r,c)self.res += 1if 0<= r < m and 0<= c < n and grid[r][c] == 0 : # 往水域走了一格# print("shui",i,j,r,c)self.res +=1if 0<= r < m and 0<= c < n and grid[r][c] == 1: dfs(r,c)m = len(grid)if m == 0:return 0n = len(grid[0])for i in range(m): # 要區(qū)別是走過的陸地不能走還是原本就是水域不能走for j in range(n):# print(i,j)if grid[i][j] == 1:dfs(i,j)return self.resgrid=[[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] so = Solution() print(so.islandPerimeter(grid))

4.劍指 Offer 12. 矩陣中的路徑

請設(shè)計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經(jīng)過了矩陣的某一格，那么該路徑不能再次進入該格子。例如，在下面的3×4的矩陣中包含一條字符串“bfce”的路徑（路徑中的字母用加粗標出）。

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

但矩陣中不包含字符串“abfb”的路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進入這個格子。

約束：不能兩次經(jīng)過同一個點
矩陣中的每一個元素，dfs + visted矩陣，上下左右匹配當前字符，
visted矩陣通過標記字符來實現(xiàn)

遞歸前保證矩陣下標的合理性，遞歸出口由匹配情況控制
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] 都進行深度優(yōu)先匹配def dfs(i,j,word):if len(word) == 0: # word 為空字符串時,匹配完成return Trueif len(word) == 1 and board[i][j] == word[0]: # 防止[i][j]下一步都是邊界且是訪問過的情況，雖然已經(jīng)匹配，但是結(jié)果是false，[["a"]]"a"return Trueif board[i][j] != word[0]: # 第一字符不匹配，完全不用遞歸，直接輸出return Falsetmp = board[i][j] # 完全沒有考慮不能重復走 board[i][j] = Nonefor 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 Trueboard[i][j] = tmpreturn False # 第一個字符匹配了，但是后面的都不配，輸出Falsem = 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 Truereturn False # 所有遍歷過了，沒有就輸出false#[["a"]],"a" #[["a"]],"a"

5.leetcode-329. 矩陣中的最長遞增路徑

給定一個整數(shù)矩陣，找出最長遞增路徑的長度。
對于每個單元格，你可以往上，下，左，右四個方向移動。 你不能在對角線方向上移動或移動到邊界外（即不允許環(huán)繞）。

輸入: nums = [[9,9,4],[6,6,8],[2,1,1] ] 輸出: 4 解釋: 最長遞增路徑為 [1, 2, 6, 9]。

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 # 本層的深度在下層深度的基礎(chǔ)上+1return dp[i][j]m = len(matrix)if m == 0:return 0n = len(matrix[0])dp = [[0] * n for _ in range(m)] # dp[i][j] 開始的最長路徑res = 0for i in range(m):for j in range(n):res = max(res,dfs(i,j))# print(dp)return res

6.leetcode-1091. 二進制矩陣中的最短路徑

在一個 N × N 的方形網(wǎng)格中，每個單元格有兩種狀態(tài)：空（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 -1if n == 1: # [[0]]這種特殊情況return 1res = 1que = [(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 + 1que.append((r,c)) # 能走沒到終點grid[r][c] = 1 # 已經(jīng)走過的地方不能再走，不然就會一直進隊出隊res += 1 # 廣度優(yōu)先的層數(shù)return -1

總結(jié)

以上是生活随笔為你收集整理的算法(28)--矩阵搜索系列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。