第 12 题：矩阵中的路径

传送门：AcWing：矩阵中的路径。

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

• 输入的路径不为空；
• 所有出现的字符均为大写英文字母；

样例：

matrix=
[
       ["A","B","C","E"],
       ["S","F","C","S"],
       ["A","D","E","E"]
]

str="BCCE" , return "true" 

str="ASAE" , return "false"

思路：典型的 floodfill 解法，本质上是递归回溯算法。

Python 代码：

class Solution(object):
    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

    def hasPath(self, matrix, string):
        """
        :type matrix: List[List[str]]
        :type string: str
        :rtype: bool
        """
        rows = len(matrix)
        if rows == 0:
            return False
        cols = len(matrix[0])

        marked = [[False for _ in range(cols)] for _ in range(rows)]

        for i in range(rows):
            for j in range(cols):
                if self.__has_path(matrix, string, 0, i, j, marked, rows, cols):
                    return True
        return False

    def __has_path(self, matrix, word, index, start_x, start_y, marked, m, n):
        # 注意：首先判断极端情况
        if index == len(word) - 1:
            return matrix[start_x][start_y] == word[-1]
        if matrix[start_x][start_y] == word[index]:
            # 先占住这个位置，搜索不成功的话，要释放掉
            marked[start_x][start_y] = True
            for direction in self.directions:
                new_x = start_x + direction[0]
                new_y = start_y + direction[1]
                if 0 <= new_x < m and 0 <= new_y < n and not marked[new_x][new_y]:
                    if self.__has_path(matrix, word, index + 1, new_x, new_y, marked, m, n):
                        return True
            marked[start_x][start_y] = False
        return False


if __name__ == '__main__':
    matrix = [
        ["A", "B", "C", "E"],
        ["S", "F", "E", "S"],
        ["A", "D", "E", "E"]
    ]

    str = "ABCEFSADEESE"

    solution = Solution()
    result = solution.hasPath(matrix, str)
    print(result)

同 LeetCode 第 79 题，传送门：79. 单词搜索，牛客网 online judge 地址。

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

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

示例:

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

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

思路：其实就是 floodfill 算法，这是一个非常基础的算法，一定要掌握。特别要弄清楚，marked 数组的作用，一开始要占住这个位置，发现此路不通的时候，要释放掉。

Python 代码：

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, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """

        m = len(board)
        n = len(board[0])

        marked = [[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, marked, m, n):
                    return True
        return False

    def __search_word(self, board, word, index, start_x, start_y, marked, m, n):
        # 先写递归终止条件
        if index == len(word) - 1:
            return board[start_x][start_y] == word[index]

        # 中间匹配了，再继续搜索
        if board[start_x][start_y] == word[index]:
            # 先占住这个位置，搜索不成功的话，要释放掉
            marked[start_x][start_y] = True
            for direction in self.directions:
                new_x = start_x + direction[0]
                new_y = start_y + direction[1]
                if 0 <= new_x < m and 0 <= new_y < n and \
                        not marked[new_x][new_y] and \
                        self.__search_word(board, word,
                                           index + 1,
                                           new_x, new_y,
                                           marked, m, n):
                    return True
            marked[start_x][start_y] = False
        return False

Java 代码：

public class Solution {

    /**
     *       x-1,y
     * x,y-1   x,y    x,y+1
     *       x+1,y
     */
    private int[][] direct = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        int len = matrix.length;
        if (len == 0) {
            return false;
        }
        boolean[] marked = new boolean[len];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(matrix, rows, cols, str, str.length, marked, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[] matrix, int rows, int cols, char[] str, int len, boolean[] marked, int i, int j, int start) {
        // 匹配到最后，说明找到一条路径
        int index = getIndex(i, j, cols);
        if (start == len - 1) {
            return matrix[index] == str[start];
        }
        // 要特别小心！
        marked[index] = true;
        if (matrix[index] == str[start]) {
            // 当前匹配了，才开始尝试走后面的路
            for (int k = 0; k < 4; k++) {
                // 特别小心，一定是一个初始化的新的变量
                int newi = i + direct[k][0];
                int newj = j + direct[k][1];
                int nextIndex = getIndex(newi, newj, cols);
                if (inArea(newi, newj, rows, cols) && !marked[nextIndex]) {
                    // marked[nextIndex] = true; 不在这里设置
                    if (dfs(matrix, rows, cols, str, len, marked, newi, newj, start + 1)) {
                        return true;
                    }
                    // marked[nextIndex] = false; 不在这里设置
                }
            }
        }
        // 要特别小心！
        marked[index] = false;
        return false;
    }

    private int getIndex(int x, int y, int cols) {
        return x * cols + y;
    }

    private boolean inArea(int x, int y, int rows, int cols) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }

    public static void main(String[] args) {
        char[] matrix = new char[]{'a', 'b', 't', 'g',
                'c', 'f', 'c', 's',
                'j', 'd', 'e', 'h'};
        int rows = 3;
        int cols = 4;
        Solution solution = new Solution();
        char[] str = "hscfdeh".toCharArray();
        boolean hasPath = solution.hasPath(matrix, rows, cols, str);
        System.out.println(hasPath);
    }
}

Java 代码：

public class Solution {
    
    /**
     *       x-1,y
     * x,y-1   x,y    x,y+1
     *       x+1,y
     */
    private int[][] direct = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        int len = matrix.length;
        if (len == 0) {
            return false;
        }
        boolean[] marked = new boolean[len];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(matrix, rows, cols, str, str.length, marked, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[] matrix, int rows, int cols, char[] str, int len, boolean[] marked, int i, int j, int start) {
        // 匹配到最后，说明找到一条路径
        int index = getIndex(i, j, cols);
        if (start == len - 1) {
            return matrix[index] == str[start];
        }
        // 要特别小心！
        marked[index] = true;
        if (matrix[index] == str[start]) {
            // 当前匹配了，才开始尝试走后面的路
            for (int k = 0; k < 4; k++) {
                // 特别小心，一定是一个初始化的新的变量
                int newi = i + direct[k][0];
                int newj = j + direct[k][1];
                int nextIndex = getIndex(newi, newj, cols);
                if (inArea(newi, newj, rows, cols) && !marked[nextIndex]) {
                    // marked[nextIndex] = true; 不在这里设置
                    if (dfs(matrix, rows, cols, str, len, marked, newi, newj, start + 1)) {
                        return true;
                    }
                    // marked[nextIndex] = false; 不在这里设置
                }
            }
        }
        // 要特别小心！
        marked[index] = false;
        return false;
    }

    private int getIndex(int x, int y, int cols) {
        return x * cols + y;
    }

    private boolean inArea(int x, int y, int rows, int cols) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }

    public static void main(String[] args) {
        char[] matrix = new char[]{'a', 'b', 't', 'g',
                'c', 'f', 'c', 's',
                'j', 'd', 'e', 'h'};
        int rows = 3;
        int cols = 4;
        Solution solution = new Solution();
        char[] str = "hscfdeh".toCharArray();
        boolean hasPath = solution.hasPath(matrix, rows, cols, str);
        System.out.println(hasPath);
    }
}