word search

/*

n*n, n<=6; w<=15

T(n,w) <= n*n*3^(w-1) == 36*3^14 = 60000 * 81 * 36 <= 10^8 * 2

for i :
    for j :
        int w_i = 0 // next letter in w to be matched
        if w[w_i] == grid[i][j] :
            bool 2-D array vis : init to false
            vis[i][j] = true
            dfs(vis, grid, i, j, w_i + 1)


bool dfs(&vis, &grid, i, j, w_i) :
    if w_i == w.length :
        return true
    
    bool ret = false
    check all neighbours (in,jn) of (i,j) : 
        if w[w_i] == grid[in][jn] && vis[in][jn] == false:
            vis[in][jn] = true
            ret |= dfs(vis, grid, in, jn, w_i + 1)
            vis[in][jn] = false
    return ret

*/

class Solution {
public:
    int di[4] = {1,0,-1,0};
    int dj[4] = {0,1,0,-1}; //down,up,left,right
    bool dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, string& word, int par_i, int par_j, int word_counter) {
        if (word_counter == word.size()) {
            return true;
        }
        
        bool found = false;
        for (int d = 0; d < 4; d++) {
            int i = par_i + di[d];
            int j = par_j + dj[d];
            if (i >= 0 and i < board.size() and j >=0 and j < board[0].size() and word[word_counter] == board[i][j] and !visited[i][j]) {
                visited[i][j] = true;
                found |= dfs(board, visited, word, i, j, word_counter + 1);
                visited[i][j] = false;
            }
        }
        return found;
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        if (n == 0) {
            return word.empty();
        }
        int m = board[0].size();
        if (m == 0) {
            return word.empty();
        }
        
        int w_i = 0;
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (word[w_i] == board[i][j]) {
                    visited[i][j] = true;
                    if (dfs(board, visited, word, i, j, w_i + 1)) {
                        return true;
                    }
                    visited[i][j] = false;
                }
            }
        }
        return false;
    }
};