leetcode79.单词搜索（回溯dfs)、200.岛屿数量

本文主要是介绍leetcode79.单词搜索（回溯dfs)、200.岛屿数量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

79.单词搜索

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

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

示例:

board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]

给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.

这是一个使用回溯算法解决的问题，涉及的知识点有 DFS 和状态重置。

class Solution:#         (x-1,y)# (x,y-1) (x,y) (x,y+1)#         (x+1,y)directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]def exist(self, board: List[List[str]], word: str) -> bool:m = len(board)if m == 0:return Falsen = len(board[0])visited = [[False for _ in range(n)] for _ in range(m)]for i in range(m):for j in range(n):# 对每一个格子都从头开始搜索if self.__search_word(board, word, 0, i, j, visited, m, n):return Truereturn Falsedef __search_word(self, board, word, index,start_x, start_y, visited, m, n):# 先写递归终止条件if index == len(word) - 1:return board[start_x][start_y] == word[index]# 中间匹配了，再继续搜索if board[start_x][start_y] == word[index]:# 先占住这个位置，搜索不成功的话，要释放掉visited[start_x][start_y] = Truefor direction in self.directions:new_x = start_x + direction[0]new_y = start_y + direction[1]# 注意：如果这一次 search word 成功的话，就返回if 0 <= new_x < m and 0 <= new_y < n and \not visited[new_x][new_y] and \self.__search_word(board, word,index + 1,new_x, new_y,visited, m, n):return Truevisited[start_x][start_y] = Falsereturn False

200.岛屿数量
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

class Solution:#        x-1,y# x,y-1    x,y      x,y+1#        x+1,y# 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是一个常见的技巧directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]def numIslands(self, grid: List[List[str]]) -> int:m = len(grid)# 特判if m == 0:return 0n = len(grid[0])visited = [[False for _ in range(n)] for _ in range(m)]count = 0# 从第 1 行、第 1 格开始，对每一格尝试进行一次 DFS 操作for i in range(m):for j in range(n):# 只要是陆地，且没有被访问过的，就可以使用 DFS 发现与之相连的陆地，并进行标记if not visited[i][j] and grid[i][j] == '1':# count 可以理解为连通分量，你可以在深度优先遍历完成以后，再计数，# 即这行代码放在【位置 1】也是可以的count += 1self.__dfs(grid, i, j, m, n, visited)# 【位置 1】return countdef __dfs(self, grid, i, j, m, n, visited):visited[i][j] = Truefor direction in self.directions:new_i = i + direction[0]new_j = j + direction[1]if 0 <= new_i < m and 0 <= new_j < n and not visited[new_i][new_j] and grid[new_i][new_j] == '1':self.__dfs(grid, new_i, new_j, m, n, visited)if __name__ == '__main__':grid = [['1', '1', '1', '1', '0'],['1', '1', '0', '1', '0'],['1', '1', '0', '0', '0'],['0', '0', '0', '0', '0']]solution = Solution()result = solution.numIslands(grid)print(result)