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

class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};

    bool dfs(vector<vector<char>>& board, const string& word, int u, int i, int j, vector<vector<bool>>& st) {
        if (u == word.size()) {
            return true;
        }
       
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || st[i][j] || board[i][j] != word[u]) {
            return false;
        }

        st[i][j] = true;

        for (int k = 0; k < 4; ++k) {
            if (dfs(board, word, u + 1, i + dx[k], j + dy[k], st)) {
                return true; 
            }
        }

        st[i][j] = false;
        return false; 
    }

    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int n = board.size(), m = board[0].size();
        vector<vector<bool>> st(n, vector<bool>(m, false));

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (dfs(board, word, 0, i, j, st)) {
                    return true;
                }
            }
        }

        return false;
    }
};