微软面试题： LeetCode 79. 单词搜索 出现次数：2

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 class Solution {
 4 public:
 5     bool exist(vector<vector<char>>& board, string word)
 6     {
 7        const int m = board.size();
 8        const int n = board[0].size();
 9        dx = {0,1,0,-1};
10        dy  = {-1,0,1,0};
11        flag.assign(m,vector<int>(n,0));
12        word.reserve();
13        for(int i = 0;i < m;++i)
14        {
15            for(int j = 0;j < n;++j)
16            {
17                if(board[i][j] == word[word.size() - 1])
18                {
19                    bool exit = dfs(board,i,j,word);
20                    if(exit)
21                    {
22                        return true;
23                    }
24                }
25            }
26        }
27        return false;
28     }
29 
30     bool dfs(vector<vector<char>>& board,int i,int j,string &word)
31     {
32         if(word == "")
33         {
34             return true;
35         }
36         if(!(i>=0 && i < board.size() && j >= 0 && j< board[0].size()))
37         {
38             return false;
39         }
40         char c = word[word.size() - 1];
41         if(flag[i][j] == 1 || board[i][j] != c)
42         {
43             return false;
44         }
45         //前进，标记访问过的路径
46         flag[i][j] = 1;
47         word.pop_back();
48         for(int k = 0; k < 4 ;++k)
49         {
50            bool res = dfs(board,i + dx[k],j + dy[k],word);
51            if(res) 
52            {
53                return true;
54            }
55         }
56         //回退，状态重置
57         flag[i][j] = 0;
58         word.push_back(c);
59         return false;
60     }
61 private:
62     vector<vector<int> > flag;
63     vector<int> dx;
64     vector<int> dy;
65 };