剑指offer65

矩阵中的路径

题目描述

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

a	b	c	e
s	f	c	s
a	d	e	e

示例

输入

“ABCESFCSADEE”,3,4,”ABCCED”

输出

true

输入

“ABCESFCSADEE”,3,4,”ABCB”

输出

false

思路

分析：回溯算法

这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的
第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。

重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。

由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。

由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。

当矩阵中坐标为（row,col）的格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。

一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置。

代码

用递归来实现DFS

1.确定出口：

false:

1.边界条件不满足；
2.当前字符不匹配；
3.已经遍历过

true：

字符串str已经遍历结束

2.递：设置访问过

递归方式，按照上下左右递归

3.归：复位，未访问

public class Solution{
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        //标志位，初始化为false
        boolean[] visited = new boolean[matrix.length];
        for (int j = 0; j < rows; j++) {
            for (int i = 0; i < cols; i++) {//每个节点都有可能是起点
                if(dfs(matrix,rows,cols,str,i,j,0,visited)) return true;
            }//这里多了个k=0来充当str的索引
        }
        return false;
    }
//递归开始
//(初始矩阵，矩阵行数rows，矩阵列数cols，待判断的字符串，索引行坐标i，索引纵坐标j，字符串索引初始为0即先判断字符串的第一位，是否访问过)
private boolean dfs(char[] matrix, int rows, int cols, char[] str, int i, int j, int k,
            boolean[] visited) 
        {
        //先根据i和j计算匹配的第一个元素转为一维数组的位置
        int index = i+cols*j;
        //递归终止条件
        if(
            i < 0
            || i >= cols
            || j < 0
            || j >= rows 
            || visited[index]
            || matrix[index] != str[k]
        )return false;
        if(k == str.length - 1) return true;//出口
        //要走的第一个位置置为true，表示已经走过了
        visited[index] = true;
        //递
        //回溯，递归寻找，每次找到了就给k加一，找不到，还原
        if(
            dfs(matrix, rows, cols, str, i, j - 1, k + 1, visited)
            || dfs(matrix, rows, cols, str, i + 1, j, k + 1, visited)
            || dfs(matrix, rows, cols, str, i, j + 1, k + 1, visited)
            || dfs(matrix, rows, cols, str, i - 1, j, k + 1, visited)
        )return true;
        //归
        //走到这，说明这一条路不通，还原，再试其他的路径
        visited[index] = false;
        return false;
        }
}