Grid / path search (Backtracking Sub-pattern)

// Grid path: mark the cell on the way in, unmark on the way out,
// so other paths may still pass through it later (Word Search).
bool dfs(vector<vector<char>>& g, const string& word, int i, int r, int c) {
    if (i == (int)word.size()) return true;              // every letter matched
    if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size() || g[r][c] != word[i])
        return false;                                    // off the grid, used, or wrong letter
    char saved = g[r][c];
    g[r][c] = '#';                                       // mark: in use on this path
    bool found = dfs(g, word, i + 1, r + 1, c) || dfs(g, word, i + 1, r - 1, c) ||
                 dfs(g, word, i + 1, r, c + 1) || dfs(g, word, i + 1, r, c - 1);
    g[r][c] = saved;                                     // unmark: free for other paths
    return found;
}

bool exist(vector<vector<char>>& board, const string& word) {
    for (int r = 0; r < (int)board.size(); r++)
        for (int c = 0; c < (int)board[0].size(); c++)
            if (dfs(board, word, 0, r, c)) return true;
    return false;
}