1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
public:
    bool result;
    bool exist(vector<vector<char>> &board, string word) {
        vector<vector<int>> flag;
        flag.clear();
        for(int i = 0; i < board.size(); i++) {
            vector<int> item(board[i].size(), 0);
            flag.push_back(item);
        }
        result = false;
        int pos = 0;
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[i].size(); j++) {
                if(flag[i][j] == 0 && board[i][j] == word[pos]) {
                    flag[i][j] = 1;
                    pos++;
                    existStep(board, flag, word, i, j, pos);
                    pos--;
                    flag[i][j] = 0;
                }
            }
        }
        return result;
    }
private:
    void existStep(vector<vector<char>> &board, vector<vector<int>> &flag, string word, int x, int y, int pos) {
        if(result) return;
        if(pos >= word.length()) {
            result = true;
            return;
        }
        int walk[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for(int i = 0; i < 4; i++) {
            int xn = x + walk[i][0];
            int yn = y + walk[i][1];
            if(xn < 0 || xn >= board.size() || yn < 0 || yn >= board[0].size()) continue;
            if(flag[xn][yn] == 1 || board[xn][yn] != word[pos]) continue;
            flag[xn][yn] = 1;
            pos++;
            existStep(board, flag, word, xn, yn, pos);
            pos--;
            flag[xn][yn] = 0;
        }
    }
};