79. Word Search

My intuition is using DFS. However, when I was implementing in first place, I didn't track if a character has been visited before. This failure to check will cause LTE if there is a loop in the matrix.
We can change the characters in the board to tag them as visited and change them back when DFS is done.

1:  class Solution {  
2:  public:  
3:    bool exist(vector<vector<char>>& board, string word) {  
4:      for (int i = 0; i < board.size(); i++) {  
5:        for (int j = 0; j < board[0].size(); j++) {  
6:          if (search(board, word, 0, i, j)) return true;  
7:        }  
8:      }  
9:      return false;  
10:    }  
11:    bool search(vector<vector<char>> &board, string word, int k, int i, int j) {  
12:      if (i < 0 || j < 0 || i == board.size() || j == board[0].size() || board[i][j] == 0 || word[k] != board[i][j])  
13:        return false;  
14:      if (word[k+1] == 0) return true;  
15:      char c = board[i][j];  
16:      board[i][j] = 0;  
17:      if (search(board, word, k+1, i-1, j) || search(board, word, k+1, i, j-1) ||  
18:        search(board, word, k+1, i+1, j) || search(board, word, k+1, i, j+1)) {  
19:        return true;  
20:      }  
21:      board[i][j] = c;  
22:      return false;  
23:    }  
24:  };