剑指Offer12:矩阵中的路径

缺乏、安全感 2022-02-18 16:55 212阅读 0赞

请设计一个函数，用来判断矩阵中是否存在包含某一条字符串的所有路径，路径可以从任意一格开始，上下左右，一条路径经过矩阵某一格，不可以再次进入。在

char[][] nums= {
      {'a','b','t','g'},{'c','f','c','s'},{'j','d','e','h'}}; 有一个bfce的路径,判断是否存在，存在返回true，不存在返回false。

思路:有点想深度搜索的，不过确实用到了深度搜索的方法。首先建立一个二维访问数组，未访问置0，访问后置1，然后从二维数组第一个开始遍历，这里你可以换成其它的点开始遍历

参数，其中比较重要的是row,col,以及pathLength，这个3个参数，row,col代表当前迭代查询的起点，pathLength则是边界，在函数中回溯框架刚开始的点就是判断当前问题是否解决，解决的就返回结束这个函数。

接下来就是处理函数的逻辑，判断当前点的边界问题，点是否满足，没满足就直接退出，迭代下一个点，满足就当前点置1，pathLength++，从这个点开始深度遍历，上下左右，直到子递归满足条件时，不断返回true,最后结束函数，如果子函数的上下左右，邻接点都没满足则返回，false,同时要从刚试探的点开始回溯，根据题干来回溯，这里就是row,col置0，pathLength--.为啥row,col置0呢，意思是从目前的点出发没找到，就应该从n-1点开始找，而刚开始pathLength都是0进入的，满足其中一个点或者已经进入子递归的过程，pathLength>0，这个时候回溯才显得有意义。

回溯的大体框架就是, 1. 边界条件判断，满足就返回，不满足就开始处理.

2.开始试探，当前点试探成功，开始递归试探（当试探的点不满足条件时必须在这一情况里面开始回溯，回溯这个情况只建立在已经进入子递归的情况下才显得有意义），当前点不成功结束整个函数,

代码:

package com.hnist.lzn.jinazhioffer;
    
    public class LookTEOnumber {
    
    
        public boolean isDown(char[][] nums,int rows,int cols,String ms){
    
            char[] string = ms.toCharArray();
    
            int[][] number = new int[rows][cols];
    
            int pathLength = 0;
            for(int i=0;i<rows;i++)
                for(int j=0;j<cols;j++){
    
                    if(Uplower(nums,nums.length,nums[0].length,i,j,number,string,0)){
    
                        return true;
                    }
    
                }
    
            return false;
        }
    
    
        public boolean Uplower(char[][] nums,int rows,int cols,int row,int col,int[][] number,char[] string,int pathLength){
    
            //怎么查找
            //开始都是边界条件,满足条件就退出
            if(pathLength==string.length-1){
    
                return true;
            }
            boolean haPath = false;
            //然后就是每一次的操作，查找当前字符是符合条件吗,并且没有被查找过
            if(col>=0&&col<cols&&row>=0&&row<rows&&nums[row][col]==string[pathLength]&&number[row][col]==0){
    
                //才能继续上下左右递归查找，那个地方开始回溯呢？？？
                 //符合条件先++
                pathLength++;
                //二维数组置1
                number[row][col] = 1;
    
                //从这个点上下左右进行满足条件的递归。我觉得每次满足条件一次应该二维数组置0才对？？？
                //递归是否有返回值，有返回值必须每次调用的时候，拿值去接受
              haPath =  Uplower(nums,rows,cols,row-1,col,number,string,pathLength)||Uplower(
                        nums,rows,cols,row+1,col,number,string,pathLength)||Uplower(
                        nums,rows,cols,row,col-1,number,string,pathLength)||
                        Uplower(nums,rows,cols,row,col+1,number,string,pathLength);
    
    
                if(!haPath){
                    //回溯的点
                    --pathLength;
                    number[row][col] = 0;
    
                }
    
    
    
    
            }
                return haPath;
    
                //上面是满足就递归，回溯的点就是当前的点如果不满足条件，就返回到上次调用它的点
    
    
        }
    
    
    
        public static void main(String[] args) {
    
            char[][] nums= {
       {'a','b','t','g'},{'c','f','c','s'},{'j','d','e','h'}};
    
            System.out.println(new LookTEOnumber().isDown(nums,3,4,"bfce"));
    
    
        }
    
    
    }