Trace a word through a grid, moving to adjacent cells, never reusing one. DFS follows a promising path letter by letter and backtracks the instant the next character doesn't match.
From each cell matching the first letter, DFS into the 4 neighbors seeking the next letter. Temporarily mark the cell used (so the path can't cross itself), recurse, then unmark on the way back.
bool dfs(vector<vector<char>>& b, int r, int c,
string& word, int k) {
if (k == word.size()) return true; // all letters matched
if (r < 0 || c < 0 || r >= b.size() || c >= b[0].size())
return false; // off the grid
if (b[r][c] != word[k]) return false; // wrong letter
char tmp = b[r][c];
b[r][c] = '#'; // mark visited
bool found = dfs(b, r+1, c, word, k+1) ||
dfs(b, r-1, c, word, k+1) ||
dfs(b, r, c+1, word, k+1) ||
dfs(b, r, c-1, word, k+1);
b[r][c] = tmp; // UNMARK (backtrack)
return found;
}
bool exist(vector<vector<char>>& b, string word) {
for (int r = 0; r < b.size(); r++)
for (int c = 0; c < b[0].size(); c++)
if (dfs(b, r, c, word, 0)) return true;
return false;
}Every cell as a start, 4 directions per step, word length L.
Recursion depth equals the word length.
Mismatch kills a branch immediately, that's what tames the 4ᴸ.
'#' blocks revisiting during this path, and restoring it lets other paths reuse the cell.