剑指 Offer 12. 矩阵中的路径

分析

其实就是个深度优先搜索。可以设置一个visit数组，标记已经走过的路段。注意判断dfs的退出条件。
写递归就是这样，先想好退出条件，再不断的缩小问题规模，就这样。

深度优先搜索法

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if len(board) == 0 or len(board[0]) == 0: return word == ''
        x,y = len(board), len(board[0])
        visited = [[False for i in range(y)] for j in range(x)]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(visited, i, j, board, word):
                    return True
        return False
    def dfs(self, visited, x, y, board, word):
        if not word: return True
        target = word[0]
        if target != board[x][y]: return False
        if not word[1:]: return True
        visited[x][y] = True
        if x-1>=0 and not visited[x-1][y]:
            flag = self.dfs(visited, x-1, y, board, word[1:])
            if flag: return flag
        if x+1 < len(board) and not visited[x+1][y]:
            flag = self.dfs(visited, x+1, y, board, word[1:])
            if flag: return flag
        if y-1>=0 and not visited[x][y-1]:
            flag = self.dfs(visited, x, y-1, board, word[1:])
            if flag: return flag
        if y+1<len(board[0]) and not visited[x][y+1]:
            flag = self.dfs(visited, x, y+1, board, word[1:])
            if flag: return flag
        visited[x][y] = False
        return False