[每日一道小算法（二十）] [回溯法] 矩阵中的路径

深藏阁楼爱情的钟 2023-07-04 12:35 15阅读 0赞

前言：  
这道题对我来说，挺难的，做了好几个小时了，唉，算法真的是太难了，慢慢来吧!!!

### 题目描述 ###

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

### 解题思路 ###

这是一个可以用回溯法来解决的典型问题。  
先来看一看什么是回溯法吧。  
回溯算法的基本思想：从一条路往前走，不能进则退回来，换一条路再试。  
正好跟这一道题挺像的，如果当前字符符合，则接着往下走，如果不合适，那么将退回来，换一条路径。  
由于回溯法的递归特性，路径可以被堪称一个栈。当在路径中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个只好在路径上回到第n-1个字符，重新定位第n个字符。  
我们还需要定义一个布尔型数组，来做路径标识，具体实现看如下代码。

### 代码样例 ###

package com.asong.leetcode.MatrixPath;
    
    public class Solution1 { 
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
        { 
            //边界条件
            if(matrix==null||matrix.length==0||rows<=0||cols<=0||str.length==0||str==null||(rows*cols)!=matrix.length){ 
                return false;
            }
            //定一个矩阵来进行坐标识
            //标记数组，记录节点都是被访问，初始化都是false
            boolean[] visited = new boolean[matrix.length];
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    if(Judge(matrix,rows,cols,i,j,str,visited,0))
                    { 
                        return true;
                    }
                }
            }
            return false;
    
        }
        //定义Judge()方法判断从字符串得第一个字符开始
        //i,j分别表示当前索引的位置
        public static boolean Judge(char[] matrix,int rows,int cols,int row,int col,char[] str,boolean[] visited,int k)
        { 
            int index = row*cols+col;
    
            //递归终止条件
            if(row<0||col<0||row>=rows||col>=cols||matrix[index]!=str[k]||visited[index]==true){ 
                return false;
            }
    
            if(k == str.length-1)
            { 
                return true;
            }
            //标记
            visited[index] = true;
    
            if(Judge(matrix,rows,cols,row-1,col,str,visited,k+1)||
                Judge(matrix,rows,cols,row,col-1,str,visited,k+1)||
                Judge(matrix,rows,cols,row+1,col,str,visited,k+1)||
                Judge(matrix,rows,cols,row,col+1,str,visited,k+1))
            { 
                return true;
            }
            visited[index] =false;
            return false;
    
        }
    }