题目描述

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

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

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

注意：

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

样例

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

str="BCCE" , return "true" 

str="ASAE" , return "false" 

C++ 代码

class Solution {
public:

    void dfs(vector<vector<char>>& matrix, const string &str,vector<vector<int>> &v, int i, int j, int cur, bool &res)
    {

        if(i < 0 || i > v.size()-1 || j < 0 || j > v.front().size()-1 || (v[i][j] == 1))
            return ;

        if(matrix[i][j] != str[cur]) return;
        v[i][j] = 1;
        if(matrix[i][j] == str[cur] && cur == (str.size()-1)) res = true;

        dfs(matrix,str,v,i-1,j,cur+1,res);
        dfs(matrix,str,v,i+1,j,cur+1,res);
        dfs(matrix,str,v,i,j-1,cur+1,res);
        dfs(matrix,str,v,i,j+1,cur+1,res);
    }

    bool hasPath(vector<vector<char>>& matrix, string &str) {
        bool res = false;
        vector<vector<int>> v(matrix.size());
        for (int i = 0; i < matrix.size(); i++)
            v[i].resize(matrix.front().size());

        for(int i = 0; i < matrix.size(); i++)
        {
            for(int j = 0; j < matrix.front().size(); j++)
            {
                if(matrix[i][j] == str[0])
                {
                    for(int i = 0; i < matrix.size(); i++)
                    {
                        for(int j = 0; j < matrix.front().size(); j++)
                        {
                               v[i][j] = 0;
                        }
                    }
                    dfs(matrix,str,v,i,j,0,res);
                }
            }
        }
        return res;
    }
};