10.矩阵中的路径

本题知识点:数组

题目描述

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

[abcesfcsadee]\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))
}

引用声明

该题目引用自
牛客网