matrix_path

class Solution {
public:
    int m;
    int n;
    vector<vector<char>> board;
    vector<vector<bool>> visited;
    bool dfs(int curx, int cury, string &word, int curp, vector<vector<bool>> &visited){
        if(curp == word.size()) return true;
        if(curx < 0 || cury < 0 || curx >= m || cury >= n) return false;
        if(visited[curx][cury] || board[curx][cury] != word[curp]) return false;
        visited[curx][cury] = true;
        return  dfs(curx, cury + 1, word, curp + 1, visited) ||
                dfs(curx, cury - 1, word, curp + 1, visited) ||
                dfs(curx + 1, cury, word, curp + 1, visited) ||
                dfs(curx - 1, cury, word, curp + 1, visited);
    }
    bool exist(vector<vector<char>>& board, string word) {
        this->m = board.size();
        this->n = board[0].size();
        this->board = board;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                visited.resize(m, vector<bool>(n, false));
                if(dfs(i, j, word, 0, visited)) return true;
            }
        }
        return false;
    }
};