矩阵中的路径

名字是乱打的

发布于 2021-12-22 07:01:33

1.4K00

代码可运行

文章被收录于专栏：软件工程软件工程

运行总次数：0

代码可运行

题目描述

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

思路

回溯法: 对于此题,我们需要设置一个判断是否走过的标志数组,长度和矩阵大小相等

我们对于每个结点都进行一次judge判断,且每次判断失败我们应该使标志位恢复原状即回溯

judge里的一些返回false的判断:

如果要判断的(i,j)不在矩阵里
如果当前位置的字符和字符串中对应位置字符不同
如果当前(i,j)位置已经走过了

否则先设置当前位置走过了,然后判断其向上下左右位置走的时候有没有满足要求的.

最后如果上面所有判断都没返回true,则最后恢复原状态

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        int[] flags=new int[matrix.length]; //用1标志走过
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                boolean res = helper(matrix, rows, cols, i, j, 0, str, flags);
                if (res) return true;
            }
        }
        return false;
    }
    //k指当前匹对的字串下标
    public boolean helper(char[]matrix,int rows,int cols,int i,int j,int k,char[]str,int[]flag){
        int curr=i*cols+j;
        if (i<0||i>=rows||j<0||j>=cols||flag[curr]==1||matrix[curr]!=str[k]) return false;
        if (k==str.length-1) return true;

        flag[curr]=1;

        if (helper(matrix,rows,cols,i+1,j,k+1,str,flag)||helper(matrix,rows,cols,i-1,j,k+1,str,flag)||
                helper(matrix,rows,cols,i,j+1,k+1,str,flag)||helper(matrix,rows,cols,i,j-1,k+1,str,flag)
        )return true;

        flag[curr]=0;
        return false;
    }