12. 矩阵中的路径

题目描述：

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

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

示例:

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

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

LeetCode 代码：

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0] and self.explore(board, i, j, word[1:]):
                    return True
        return False
    
    def explore(self, board, i, j, word):
        if not word:
            return True
        temp, board[i][j] = board[i][j], '#'
        success = False
        for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
            if 0<=x<len(board) and 0<=y<len(board[0]) and board[x][y]==word[0] and \
               self.explore(board, x, y, word[1:]):
                success = True
                break
        board[i][j] = temp
        return success

牛客网代码（牛客网上输入的矩阵是以字符串的形式给定的，所以需要做一些调整）：

class Solution:
    def hasPath(self, matrix, rows, cols, path):
        matrix = list(matrix)
        for i in range(rows):
            for j in range(cols):
                if matrix[i*cols+j] == path[0] and self.explore(matrix, rows, cols, i, j, path[1:]):
                    return True
        return False
    
    def explore(self, matrix, rows, cols, i, j, path):
        if not path:
            return True
        temp, matrix[i*cols+j] = matrix[i*cols+j], '#'
        success = False
        for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
            if 0<=x<rows and 0<=y<cols and matrix[x*cols+y]==path[0] and \
               self.explore(matrix, rows, cols, x, y, path[1:]):
                success = True
                break
        matrix[i*cols+j] = temp
        return success

总结：

回溯法适用于这样的问题：

• 这个问题可能要分很多步才能完成；
• 每一步都有很多种可能，而且即使这一步确定了，下一步还是会有很多种可能。

矩阵中的路径问题是典型的可以用回溯法解决的问题，通常回溯法适合用递归实现代码。当我们到达某一个节点时，尝试所有可能的选项并在满足条件的前提下递归地抵达下一个节点。