123. Word Search

Code(Language:C++) (Judger:cloudjudge-cluster-5)

class Solution {
public:
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    const vector<int> dx = {-1, 1, 0, 0};
    const vector<int> dy = {0, 0, -1, 1};
    const int dir = 4; 
    bool exist(vector<vector<char>> &board, string &word) {
        // write your code here
        const int m = board.size();
        if(m == 0){
            return false; 
        }
        const int size = word.size();
        if(size == 0){
            return false; 
        }
        const int n = board[0].size(); 
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == word[0]){
                    vector<vector<int>> visited(m, vector<int>(n, 0)); 
                    //visited[i][j] = 1; 
                    if(dfs(board, word, visited, 0, i, j)){
                        return true; 
                    }
                }
            }
        }
        return false; 
    }
    bool dfs(vector<vector<char>> &board, string &word, vector<vector<int>> &visited, int len, int x, int y){
        if(len == word.size()){
            return true; 
        }
        if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] != word[len]){
            return false; 
        }
        if(visited[x][y]){
            return false; 
        }

        visited[x][y] = 1; 
        for(int i = 0; i < dir; i++){
            
            if(dfs(board, word, visited, len + 1, x + dx[i], y + dy[i])){
                //visited[x][y] = 0; 
                return true; 
            }
        }
        visited[x][y] = 0; 
        return false; 
    }
};