LeetCode-Word Search

很简单的dfs；
 1 class Solution {
 2 public:
 3     bool exist(vector<vector<char> > &board, string word) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         if (word.empty()) {
 7             return true;
 8         }
 9         if (board.empty()) {
10             return false;
11         }
12         int m = board.size();
13         int n = board[0].size();
14         if (word.size() > m * n) {
15             return false;
16         }
17         vector<vector<bool> > visited(m, vector<bool>(n, false));
18         for (int i = 0; i < m; ++i) {
19             for (int j = 0; j < n; ++j) {
20                 if (dfs(board, visited, word, i, j, 0)) {
21                     return true;
22                 }
23             }
24         }
25         return false;
26     }
27     bool dfs(vector<vector<char> > &board, vector<vector<bool> > &visited, string &word, int r, int c, int k) {
28         if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size() || visited[r][c]) {
29             return false;
30         }
31         if (k == word.size() - 1) {
32             return (board[r][c] == word[k]);
33         }
34         if (board[r][c] != word[k]) {
35             return false;
36         }
37         visited[r][c] = true;
38         bool res = dfs(board, visited, word, r - 1, c, k + 1) || dfs(board, visited, word, r + 1, c, k + 1) || dfs(board, visited, word, r, c - 1, k + 1) || dfs(board, visited, word, r, c + 1, k + 1);
39         visited[r][c] = false;
40         return res;
41     }
42 };