LeetCode每日一题 之 矩阵中的路径

题目

image 题目地址

解题思路

这道题和之前的一道机器人走格子的算法题很像，都是根据深度优先的回溯方法解题。我们先遍历找到起点位置，再从这个起点位置，向四周深度遍历，一个方向不行，回溯到上一个结点，向其他方向发展。
这里要注意，起点在矩阵中可能由多个，如果一个起点不行，要接着遍历找下一个起点。

代码

public class Solution {
    int rows;
    int cols;
    int length;
    char[] matrix;
    char[] str;
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(str.length==0){
            return true;
        }
        this.rows=rows;
        this.cols=cols;
        length=matrix.length;
        this.matrix=matrix;
        this.str=str;
        //找起点
        for(int i=0;i<matrix.length;i++){
            if(matrix[i]==str[0]){
                //数组存储走过的结点序号，防止重复走
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                //这里如果发现这个起点不能通过，找下一个
                if(find(i,0,list)){
                    return true;
                }
            }
        }
        return false;
    }
    
    //找到起点，开始执行深度遍历并回溯
    private boolean find(int index,int k,List list){
        return
        check(index-cols,k+1,list)||
        check(index+cols,k+1,list)||
        check(index+1,k+1,list)||
        check(index-1,k+1,list);
    }
    
    private boolean check(int index,int k,List list){
        if(k == 1 && list.size() > 1){
            //回溯后，清空之前的路径数据
            list = list.subList(0,2);
        }
        if(list.contains(index)){
            //已经走过这个点
            return false;
        }
        if(k >= str.length){
            return true;
        }
        if(str.length > k && !(index < 0 || index >= length)){
            if(str[k] == matrix[index]){
                //匹配结点，如果匹配，找下一个结点
                list.add(index);
                return true && find(index , k ,list);
            }
            return false;
        }else{
            return false;
        }
    }
}