矩阵中的路径判断-Java基础

左手的ㄟ右手 2021-12-17 16:53 165阅读 0赞

## 题目描述 ##

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

![20190708204939924.png][]

解题思路：  
    1、将输入得字符数组转换为矩阵，或者直接输入二维数组；  
    2、回溯搜索所有结果进行判断是否

import java.util.ArrayList;  
import java.util.List;  
/\*\*  
 \* @author ycy  
 \* 题目描述：  
 \*   判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向上下左右移动一个格子。  
 \*   如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。  
 \* 解题思路：  
 \*    1、将输入得字符数组转换为矩阵，或者直接输入二维数组；  
 \*    2、回溯搜索所有结果进行判断是否  
 \*/  
public class matrixPath12\_77 \{  
    static int rows=3;  
    static int cols=4;  
    private final static int\[\]\[\] next = \{ \{0,-1\},\{0,1\},\{-1,0\},\{1,0\}\};//下一个元素  
      
    private static boolean backtracking(char matrix\[\]\[\],char str\[\],boolean marked\[\]\[\],int pathLen,int r,int c)\{  
        if(pathLen == str.length) return true;  
        if(r<0 || r>=rows || c<0 ||c>=cols || matrix\[r\]\[c\] != str\[pathLen\] || marked\[r\]\[c\])\{  
            return false;  
        \}  
        marked\[r\]\[c\] = true;  
        for(int\[\] n: next)\{  //代替 i, j - 1 和 i - 1, j 和 i, j + 1 和 i + 1, j  
            if(backtracking(matrix,str,marked,pathLen+1,r+n\[0\],c+n\[1\]))    //所有得下一个元素进行判断              
                return true;  
        \}  
        marked\[r\]\[c\] = false;  
        return false;  
    \}  
      
    public static boolean hasPath(char array\[\],int rows, int cols, char str\[\])\{  //判断是否包含这个路径，递归回溯  
        if(rows==0||cols==0) return false;  
        boolean marked\[\]\[\] = new boolean\[rows\]\[cols\];  
        char matrix\[\]\[\] = buildMatrix(array,rows,cols);  
        for(int i=0;i<rows;i++)  
        \{  
            for(int j=0;j<cols;j++)  
            \{  
                System.out.print(matrix\[i\]\[j\]+" ");  
                if(backtracking(matrix,str,marked,0,i,j)); //递归去找下一个                  
                    return true;  
            \}  
        \}  
        return false;  
    \}  
      
    private static char\[\]\[\] buildMatrix(char\[\] array,int rows,int cols)\{  //数组转换为矩阵  
        char\[\]\[\] matrix = new char\[rows\]\[cols\];  
        for(int i=0,idx=0;i<rows;i++)  
        \{  
            for(int j=0;j<cols;j++)\{  
                matrix\[i\]\[j\] = array\[idx++\];  
            \}  
        \}  
        return matrix;  
    \}  
    public static void main(String\[\] args) \{  
          
        char\[\] array = \{'a','b','t','g','c','f','c','s','j','d','e','h'\};  
        char str\[\] = \{'a','b','c','d'\};  
      
        char matrix\[\]\[\] = buildMatrix(array,3,4);  
        for(int i=0;i<rows;i++)\{   //矩阵打印成现  
            for(int j=0;j<cols;j++)\{  
                System.out.print(matrix\[i\]\[j\]+" ");  
            \}  
            System.out.println(" ");  
        \}                  
          
        boolean result = hasPath(array,4,3,str);   //调用测试是否存在该路径  
        System.out.print("是否存在该路径"+result);  
    \}  
\}

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[20190708204939924.png]: /images/20211213/bf0145b819a244638f272665c01f107d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211213/56ec37696d064fc7a99dd0fab73b37d1.png