题解 | #矩阵中的路径#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        int m = matrix.size();
        if(m==0)
            return false;
        int n = matrix[0].size();
        vector<vector<int> >status(m, vector<int>(n,0));
        int pos = 0;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(matrix[i][j] == word[0]){
                    if (hasPath(matrix,word,status,i,j,pos))
                        return true;
                }
            }
        }
        return false;
    }

    bool hasPath(vector<vector<char> >& matrix, string word , vector<vector<int> > status, int i, int j,int pos) {
        if(pos == word.size())
            return true;
        if(i<0 || i == matrix.size())
            return false;
        if(j<0 || j==matrix[0].size())
            return false;
        if(status[i][j] == 1)
            return false;
        if(matrix[i][j] != word[pos])
            return false;
        if(status[i][j] == 0 && matrix[i][j] == word[pos]){
            status[i][j] = 1;
            printf("%c (%d,%d)",word[pos],i,j);
        }
        return hasPath(matrix,word,status,i,j-1, pos+1)
         || hasPath(matrix,word,status,i-1,j, pos+1) 
         || hasPath(matrix,word,status,i,j+1, pos+1)
         || hasPath(matrix,word,status,i+1,j, pos+1) ;
    }
};