java语言--矩阵中的路径之算法实现

左手的ㄟ右手 2022-10-06 08:57 87阅读 0赞

1、描述：

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

**牛客连接：**[地址][Link 1]

举例：

输入：\[\[a,b,c,e\],\[s,f,c,s\],\[a,d,e,e\]\],"abcced"

返回值：true

2、解决方案1（回溯算法）：

1)、根据给定数组，初始化一个标志位数组，初始化为false，表示未走过，true表示已经走过，不能走第二次

2)、遍历二维数组（这里将二维数组变为一维数组给出），找到一个与str字符串的第一个元素相匹配的矩阵元素，进入check

3)、确定递归终止条件：若k（给定字符串的下标），已经到了给定字符串的最后一位，此时说明是匹配成功的，返回true；其余均返回false。

4)、下面就是本题的精髓，递归不断地寻找周围四个格子是否符合条件，先判断标志位为false和数组下标不能越界才能进行判断；只要有一个格子符合条件，就继续再找这个符合条件的格子的四周是否存在符合条件的格子，直到k到达末尾或者不满足递归条件就停止。

5)、若递归结果为false，说明本次是不成功的，我们要还原标志位数组index处的标志位，进入下一轮的判断。

3、 核心代码实现：

public class JZ65JuZhenZhongDeLuJing{
         
        public static void main(String[] args) {
            char[][] matrix = {
       {'a','b','c','e'},
                               {'s','f','c','e'},
                               {'a','d','e','e'}};
    
            String word = "abcced";
    
            boolean b = hasPath(matrix, word);
    
            System.out.println(b);
        }
    
        //首先不确定第一个字母的初始位置，遍历寻找一遍，找到初始位置，设置访问数组，通过一系列条件
        public static boolean hasPath (char[][] matrix, String word) {
            // 循环多次找到首个字母的初始位置
            for(int i=0;i<matrix.length;i++){
                for(int j=0;j<matrix[0].length;j++){
                    if(matrix[i][j] == word.charAt(0)){
                        //创建布尔类型的二维数组，找到初始位置，设置访问标记数组，可能不是一个，所有每次都创建新数组
                        boolean vis[][]=new boolean[matrix.length][matrix[0].length];
                         //  dfs传入初始位置，访问数组，矩阵，寻找的字符位置，字符串
                        if(dfs(i,j,vis,matrix,0,word)==true)
                            return true;
                    }
                }
            }
            return false;
        }
    
        public static boolean dfs(int m,int n,boolean[][] vis,char[][] matrix,int k,String word){
             //如果m，n位置在矩阵外返回false，如果这一节点走过返回 false
            if(m<0||n<0||m>=matrix.length||n>=matrix[0].length||vis[m][n]==true)
                return false;
               // 如果这个位置字母和字符串尾字母一样，且字符串序号就是最后一个，代表遍历完了，返回true，不在遍历
            if(word.charAt(word.length()-1) == matrix[m][n] && (k == word.length()-1))
                return true;
              // 字符串字母是序号对应字母
            if(word.charAt(k)==matrix[m][n]){
                 // 访问过了
                vis[m][n]=true;
                 // 如果上下左右有下一个字母（k+1）则继续遍历，否则访问设置为未访问（每个字母只能经过一次，没有找到下一个字母，所以没有访问过）
                if(dfs(m-1,n,vis,matrix,k+1,word)
                        ||dfs(m+1,n,vis,matrix,k+1,word)
                        ||dfs(m,n-1,vis,matrix,k+1,word)
                        ||dfs(m,n+1,vis,matrix,k+1,word)){
                    return true;
                }else{
                    vis[m][n]=false;
                    return false;
                }
            }else{  //当前不是对应字母，返回false
                vis[m][n]=false;
                return false;
            }
        }
    
    }

4、此处采用回溯算法，当然还有更多的解决方案，以后会慢慢分享，敬请期待！

[Link 1]: https://blog.csdn.net/xianlvfan2224/article/details/88911334