题解 | #矩阵中的路径#

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool find_flag =false;
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型vector<vector<>>
     * @param word string字符串
     * @return bool布尔型
     */

    // const int maxsize =1000;
    void dfs(vector<vector<char> >& matrix,int x, int y, bool vis[1000][1000], int shape_x, int shape_y,string path,const string teststr) {
        if(path == teststr ){
            find_flag =true;
        }
        if (x >= 0 && x < shape_x && y >= 0 && y < shape_y
        &&!vis[x][y]&&teststr.substr(0,path.size())==path) {
            path.push_back(matrix[x][y]);
            vis[x][y] = true;

            cout<<path<<endl;
            for (int i = 0; i < 4; i++) {
                int next_x = x + dx[i];
                int next_y = y + dy[i];
                 
                dfs(matrix,next_x, next_y, vis, shape_x, shape_y,path,teststr);

            }
            vis[x][y ] = false;
            path.pop_back();
        }


        return ;
    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // cout<<matrix.size()<<endl;
        // write code here
        bool    vis[1000][1000] = {false};

        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[i].size(); ++j) {
                dfs(matrix, i, j, vis, matrix.size(), matrix[i].size(),"",word);
            }
        }
        return find_flag? true:false;

    }
};