思路：
上下左右不停的走，能走就行，走不了就撤，设置标志位，这样就只走没走过的地方，不停的上下左右转即可。对于出界和走过的地方给予剪枝处理，剩下的继续逛街就行。
我愿称之为逛街算法。
题目1：
剑指 Offer 12. 矩阵中的路径
难度中等582收藏分享切换为英文接收动态反馈
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
提示：
1 <= board.length <= 200
1 <= board[i].length <= 200
board 和 word 仅由大小写英文字母组成
python代码：
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: def dfs(i , j , k): if not 0<= i <len(board) or not 0<= j <len(board[0]) or word[k]!=board[i][j]: return False if k == len(word)-1:return True board[i][j] = '' ans = dfs(i+1 , j , k+1) or dfs(i-1 , j , k+1) or dfs(i , j+1 , k+1) or dfs(i , j-1 , k+1) board[i][j] = word[k] return ans for i in range(len(board)): for j in range(len(board[0])): if dfs(i , j , 0): return True return False
题目2：
剑指 Offer 13. 机器人的运动范围
难度中等496收藏分享切换为英文接收动态反馈
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 100
0 <= k <= 20
python代码：
class Solution: def movingCount(self, m: int, n: int, k: int) -> int: def digital(i , j): ans = 0 while i: ans += i%10 i //= 10 while j: ans += j%10 j //= 10 return ans board = [[0 for i in range(n)] for j in range(m)] print(board) def dfs(i , j): ads = 0 if not 0<= i <len(board) or not 0<= j <len(board[0]) or not digital(i , j)<k or board[i][j]==1: return ads ads += 1 board[i][j] = 1 return dfs(i+1 , j) + dfs(i-1 , j) + dfs(i , j+1) + dfs(i , j-1) aes = 0 for i in range(m): for j in range(n): aes += dfs(i , j) return aes
417. 太平洋大西洋水流问题
难度中等436收藏分享切换为英文接收动态反馈
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
示例 1：
输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
示例 2：
输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]
提示：
m == heights.length n == heights[r].length 1 <= m, n <= 200 0 <= heights[r][c] <= 105 class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: def dfs(i , j , flag): #逛街函数 if board[i][j] == 1:return board[i][j] = 1 if flag: peace[i][j] = 1 else: west[i][j] = 1 for t in range(4): x1 = i + ans[t][0]#上下左右四个方向 y1 = j + ans[t][1] if not worled(x1 , y1):#判断有没有越界 continue if heights[x1][y1]<heights[i][j]:#水从高处流向低处，如果新位置的水比原来的还低，那么就不能流 continue dfs(x1 , y1 , flag) return def worled(i , j): #写了个函数，专门用来判断有没有越界 return 0<=i<m and 0<=j<n m = len(heights) n = len(heights[0]) result = [] board = [[0 for i in range(n)] for j in range(m)] peace = [[0 for i in range(n)] for j in range(m)] west = [[0 for i in range(n)] for j in range(m)] ans = [(-1, 0), (0, 1), (1, 0), (0, -1)] for i in range(0 , 1):#从上面的太平洋逆流 for j in range(n): dfs(i , j , True) board = [[0 for i in range(n)] for j in range(m)] for i in range(m):#左边的太平洋 for j in range(0 , 1): dfs(i , j , True) board = [[0 for i in range(n)] for j in range(m)] for i in range(m-1 , m):#下面的大西洋 for j in range(n): dfs(i , j , False) board = [[0 for i in range(n)] for j in range(m)] for i in range(m):#右边的大西洋 for j in range(n-1 , n): dfs(i , j , False) for i in range(m):#找出可以同时流向大西洋和太平洋的水 for j in range(n): if peace[i][j] == 1 and west[i][j] == 1: result.append([i , j]) return result
