Leetcode#79 Word Search

 1 bool dfs(vector<vector<char> > &board, int r, int c, string word) {

 2   int m = board.size();

 3   int n = board[0].size();

 4   int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

 5 

 6   if (word.empty())

 7     return true;

 8 

 9   if (r >= 0 && r < m && c >= 0 && c < n && board[r][c] == word[0]) {

10     for (int i = 0; i < 4; i++) {

11       char tmp = board[r][c];

12       board[r][c] = 0;

13       if (dfs(board, r + dir[i][0], c + dir[i][1], word.substr(1)))

14         return true;

15       board[r][c] = tmp;

16     }

17   }

18 

19   return false;

20 }

21 

22 bool exist(vector<vector<char> > &board, string word) {

23   if (board.empty() || board[0].empty()) return false;

24 

25   int m = board.size();

26   int n = board[0].size();

27 

28   for (int i = 0; i < m; i++)

29     for (int j = 0; j < n; j++)

30       if (dfs(board, i, j, word))

31         return true;

32 

33   return false;

34 }