10.矩阵中的路径

本题知识点：数组

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如

\begin{bmatrix} a & b & c &e \\ s & f & c & s \\ a & d & e& e\\ \end{bmatrix}

矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

a	b	c	e
s	f	c	s
a	d	e	e

解题思路

回溯法
基本思想：
0.根据给定数组，初始化一个标志位数组，初始化为false，表示未走过，true表示已经走过，不能走第二次
1.根据行数和列数，遍历数组，先找到一个与str字符串的第一个元素相匹配的矩阵元素，进入judge
2.根据i和j先确定一维数组的位置，因为给定的matrix是一个一维数组
3.确定递归终止条件：越界，当前找到的矩阵值不等于数组对应位置的值，已经走过的，这三类情况，都直接false，说明这条路不通
4.若n，就是待判定的字符串str的索引已经判断到了最后一位，此时说明是匹配成功的
5.下面就是本题的精髓，递归不断地寻找周围四个格子是否符合条件，只要有一个格子符合条件，就继续再找这个符合条件的格子的四周是否存在符合条件的格子，直到k到达末尾或者不满足递归条件就停止。
6.走到这一步，说明本次是不成功的，我们要还原一下标志位数组index处的标志位，进入下一轮的判断。

代码实现

java 代码

    /**
     * 回溯法查找路径是否存在
     * @param matrix 矩阵数组
     * @param rows 矩阵行数
     * @param cols 矩阵列数
     * @param str 查找字符串路径数组
     * @return
     */
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        //创建和矩阵相同大小的标志位数组
        boolean[] flag = new boolean[matrix.length];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                //查找字符串路径的起始位，开始向四周搜索路径
                if(judge(matrix, rows, cols, i, j, str, 0, flag)){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 回溯法查找路径是否存在
     * @param matrix 矩阵数组
     * @param rows 矩阵行数
     * @param cols 矩阵列数
     * @param i 当前行数坐标
     * @param j 当前列数坐标
     * @param str 查找字符串路径数组
     * @param n 当前字符串数组中查到当前位数
     * @param flag 标记路径中是否已经进入的标志
     * @return
     */
    public boolean judge(char[] matrix, int rows, int cols, int i, int j, char[] str, int n, boolean[] flag) {
        //判断当前坐标是否越界，如果越界，则不在矩阵内，返回false
        if (i < 0 || j < 0 || i >= rows || j >= cols) {
            return false;
        }
        //根据矩阵坐标转换为数组下标
        int index = i * cols + j;
        //判断盖数组下标的格子是否已经进入，如果进入，则不能再次进入，返回false
        if (flag[index]) {
            return false;
        }
        //判断查找的字符串路径当前字符与数组中当前下标的字符是否相同，如果不相同，则当前格子不存在路径，返回false
        if (str[n] != matrix[index]) {
            return false;
        }
        //判断已经查找到字符串最后一位，则路径存在，返回true
        if (n + 1 == str.length) {
            return true;
        }
        //当前位置表示当前格子符合字符串查找路径中当当前位置n，将该格子标记为true，避免下一个格子搜索时进入
        flag[index] = true;
        //开始搜索字符串查找路径当前位置的下一个字符路径，分布查找当前格子上，下，左，右的格子是否存在下一个字符的路径
        if (judge(matrix, rows, cols, i - 1, j, str, n + 1, flag)
                || judge(matrix, rows, cols, i + 1, j, str, n + 1, flag)
                || judge(matrix, rows, cols, i, j - 1, str, n + 1, flag)
                || judge(matrix, rows, cols, i, j + 1, str, n + 1, flag)
        ) {
            //下一个字符路径存在，则当前格子路径正确，返回true
            return true;
        } else {
            //下一个字符路径不存在，当前格子路径不正确，则将当前格子标志位置为false(回溯),可以允许其他格子检查时进入
            flag[index] = false;
            return false;
        }
    }

    public static void main(String[] args){
         char[] matrix = {'a','b','c','e','s','f','c','s','a','d','e','e'};
        int rows = 3;
        int cols = 4;
        char[] str = "bccfd".toCharArray();
        System.out.println(hasPath(matrix,rows,cols,str));
    }

Kotlin 代码

     /**
     * 回溯法查找路径是否存在
     * @param matrix 矩阵数组
     * @param rows 矩阵行数
     * @param cols 矩阵列数
     * @param i 当前行数坐标
     * @param j 当前列数坐标
     * @param str 查找字符串路径数组
     * @param n 当前字符串数组中查到当前位数
     * @param flag 标记路径中是否已经进入的标志
     * @return
     */
    private fun judge(
        matrix: CharArray,
        rows: Int,
        cols: Int,
        i: Int,
        j: Int,
        str: CharArray,
        n: Int,
        flag: BooleanArray
    ): Boolean {
        //判断当前坐标是否越界，如果越界，则不在矩阵内，返回false
        if (i < 0 || j < 0 || i >= rows || j >= cols) {
            return false
        }
        //根据矩阵坐标转换为数组下标
        val index = i * cols + j
        //判断盖数组下标的格子是否已经进入，如果进入，则不能再次进入，返回false
        if (flag[index]) {
            return false
        }
        //判断查找的字符串路径当前字符与数组中当前下标的字符是否相同，如果不相同，则当前格子不存在路径，返回false
        if (str[n] != matrix[index]) {
            return false
        }
        //判断已经查找到字符串最后一位，则路径存在，返回true
        if (n + 1 == str.size) {
            return true
        }
        //当前位置表示当前格子符合字符串查找路径中当当前位置n，将该格子标记为true，避免下一个格子搜索时进入
        flag[index] = true
        //开始搜索字符串查找路径当前位置的下一个字符路径，分布查找当前格子上，下，左，右的格子是否存在下一个字符的路径
        return if (judge(matrix, rows, cols, i - 1, j, str, n + 1, flag)
            || judge(matrix, rows, cols, i + 1, j, str, n + 1, flag)
            || judge(matrix, rows, cols, i, j - 1, str, n + 1, flag)
            || judge(matrix, rows, cols, i, j + 1, str, n + 1, flag)
        ) {
            //下一个字符路径存在，则当前格子路径正确，返回true
            true
        } else {
            //下一个字符路径不存在，当前格子路径不正确，则将当前格子标志位置为false(回溯),可以允许其他格子检查时进入
            flag[index] = false
            false
        }
    }

    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        val matrix =
            charArrayOf('a', 'b', 'c', 'e', 's', 'f', 'c', 's', 'a', 'd', 'e', 'e')
        val rows = 3
        val cols = 4
        val str = "bccfd".toCharArray()
        println(hasPath(matrix, rows, cols, str))
    }

引用声明

该题目引用自
牛客网