[剑指 Offer 第 2 版第 12 题] “矩阵中的路径”做题记录

第 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);
        }
    }

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/