【剑指 offer】矩阵中的路径（DFS）

1、题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

• 注意：

输入的路径不为空；
所有出现的字符均为大写英文字母；

• 样例

matrix=
[
   ["A","B","C","E"],
   ["S","F","C","S"],
   ["A","D","E","E"]
]

• str="BCCE" , return "true"
• str="ASAE" , return "false"

2、问题描述：

3、问题关键：

• 典型的DFS应用。最重要的就是考虑好搜索路径。

• 先枚举单词的起点， 再依次枚举单词的每个字母。

• 避免重复使用，将使用过的改成一个 特殊的字母，完了记得修改回来。

• 时间复杂度: 。

4、C++代码：

class Solution {
public:
    bool hasPath(vector<vector<char>>& matrix, string str) {
        for (int i = 0; i < matrix.size(); i ++) //依次遍历每一个点为起点。
            for (int j = 0; j < matrix[0].size(); j ++) 
                if (dfs(matrix, str, 0, i, j)) return true;//如果存在一条路径，那么就返回true。
        return false;//一条路径都不存在。
    }
    bool dfs(vector<vector<char>> &matrix, string &str, int u, int x, int y) {
        if (matrix[x][y] != str[u]) return false;//如果比较到某一个结点不行，当前路径不可以。
        if (u == str.size() - 1) return true;//如果遍历到str的最后一个结点还相同的话，直接返回true。
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//定义遍历的四个方向。
        char t = matrix[x][y];//保存遍历过的点。
        matrix[x][y] = '*';//将遍历过的结点做一个标记。
        for (int i = 0; i < 4; i ++) {//依次枚举四个方向。
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()){//如果还在区域内那么继续枚举。
                if (dfs(matrix, str, u + 1, a, b)) return true;//找到一条路径就返回。
            }
        }
        matrix[x][y] = t;//恢复现场，说明当前起点没有路径。
        return false;
    }
};