题解 | 单词搜索

class Solution {
public:
    vector<vector<int>> direction = {{0, -1},{-1, 0},{0, +1},{+1, 0} };  //左上右下
    vector<vector<int>> used;  //防止一次检验字符串时，重复搜索

    bool exist(vector<string>& board, string word) {
        used.resize(board.size(), vector<int>( board[0].size(), 0) );  //初始化

        for(int i=0 ; i < board.size(); ++i){
            for(int j =0; j < board[0].size(); ++j){
                if( dp(board, word, 0, i, j) ){
                    return true;
                }
            }
        }
        
        return false;
    }

    bool dp(vector<string> &board, string& word, int index, int i, int j){   //输入需要验证的坐标
        if(i<0 || i>=board.size() || j<0 || j>board[0].size() || used[i][j] || word[index] != board[i][j])return false;

        if(index == word.size()-1){
            return true;
        }

        used[i][j] = 1;  //使用了本元素；
        for(int k =0; k<4; ++k){
            if( dp(board, word, index+1, i+direction[k][0], j+direction[k][1]) ){
                return true;
            }
        }
        used[i][j] = 0;  //还原
        return false;
    }
};