题目描述

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

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

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

注意：

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

样例

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

str="BCCE" , return "true" 

str="ASAE" , return "false"

算法

(DFS)

1. 这道题和字母这题很像，但是有几点不同。

   • 第一个是 字母这道题中，恢复现场使用st[]是可以的，但是这道题需要是st[][]，不知道为什么，一直SE。
   • 在递归到下一层u + 1的时候，一定要判断if(!st[a][b] && matrix[a][b] == s[u])，缺一不可，因为这道题规定 每个字符 是一定要 匹配上的。

2. 在DFS中，最重要的就是考虑好搜索顺序。
3. 先枚举单词的首字母s[0]，然后这时候匹配了1个字符，所以u = 1，u就是 匹配的字符数量 ，然后依次枚举单词 剩下的每个字母 。
4. 这道题u是从1开始枚举的。u是已经匹配的字符个数。

时间复杂度

$O(n^23^k)$

• 单词的起点一共有$n^2$个，矩阵中的每个字符都有 上下左右4个方向可以走，但是 不能往回走，所以只剩下3个方向，其中的k表示路径的平均长度。

C++ 代码

class Solution {
public:
    bool st[1010][1010];
    string s;
    vector<vector<char>> matrix;
    int n, m;

    bool dfs(int u, int x, int y)
    {
        if(u == s.size()) return true;
        st[x][y] = true;

        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        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(!st[a][b] && matrix[a][b] == s[u])
                {
                    bool res = dfs(u + 1, a, b);
                    if(res) return true;
                }
            }
        }

        st[x][y] = false;
        return false;
    }

    bool hasPath(vector<vector<char>>& mat, string &str) 
    {
        if(mat.size() == 0 || mat[0].size() == 0) return false;
        s = str;
        matrix = mat;
        for(int i = 0; i < mat.size(); i ++)
            for(int j = 0; j < mat[i].size(); j ++)
                if(mat[i][j] == s[0] && dfs(1, i, j))
                    return true;
        return false;
    }
};