题解 | 矩阵中的路径 递归

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool check(vector<vector<int>> v,vector<vector<char>>& matrix,int i, int j,int index,string& word)
    {
        int row=matrix[0].size();
        int column=matrix.size();
        
        bool result=false;
        if(index>=word.size())
        {
            return true;
        }
        if(i<0||i>=column||j<0||j>=row)
        {
            return false;
        }
        if(v[i][j]!=-1&&matrix[i][j]==word[index])
        {
            result=true;
            v[i][j]=-1;
        }
        return result&&(check(v,matrix,i,j+1,index+1,word)||
        check(v,matrix,i,j-1,index+1,word)||
        check(v,matrix,i-1,j,index+1,word)||
        check(v,matrix,i+1,j,index+1,word));
    }

    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        // resize(大小),默认初始化为0；
        // vector 默认为0
        int row=matrix[0].size();
        int column=matrix.size();
        
        for(int i=0;i<column;i++)
        {
            for(int j=0;j<row;j++)
            {
                vector<vector<int>> flag(matrix.size(),vector<int>(matrix[0].size()));
                if(check(flag,matrix,i,j,0,word))
                return true;

            }
        }
        
        return false;
    }
};