这是典型的DFS搜索问题，这里有一个技巧是，不需要每次都用一个visited数组来判断是否遍历过，直接用在原地修改，然后进行回溯，走过，就把当前格点换位‘.'，之后再复原。
const int dx[]={1,0,-1,0}; const int dy[]={0,1,0,-1}; class Solution { public: bool exist(vector<vector<char>>& board, string word) { for(int i=0;i<board.size();i++){ for(int j=0;j<board[0].size();j++){ if(dfs(board,i,j,word,0)){ return true; } } } return false; } bool dfs(vector<vector<char>>& board, int x, int y, string word, int k){ if(board[x][y]!=word[k]) return false; if(k==word.size()-1) return true; char t = board[x][y]; board[x][y] = '*'; for(int i=0;i<4;i++){ int a = x + dx[i]; int b = y + dy[i]; if(a>=0&&a<board.size()&&b>=0&&b<board[0].size()&&dfs(board,a,b,word,k+1)) return true; } board[x][y] = t; return false; } };
