https://oj.leetcode.com/problems/word-search/
类似于在棋盘上走步，走过的地方不能再走，每次都可以走当前位置的上、下、左、右，问能不能走出要求的形状来。
深搜：
依次搜它的上
下
左
右
在深搜中，容易超时，所以如果有复杂类型的数据传值，一般都用引用。当然，为了恢复每次引用的现场，需要把本次深搜中改变的值，再改回来。
class Solution { public: bool exist(vector<vector<char> > &board, string word) { if(board.size() == 0 || word.size() == 0) return false; int row = board.size(); int col = board[0].size(); vector<vector<bool> > flag; //initialize flag.resize(row); for(int i = 0; i < row; i++) { flag[i].resize(col); for(int j = 0; j < col; j++) flag[i][j] = false; } bool ans = false; for(int i = 0; i < row; i++) { for(int j = 0; j < col; j++) { if(board[i][j] == word[0]) { ans = find(board,word,i,j,flag,1); if(ans) return true; } } } return false; } bool find(vector<vector<char> > &board, string &word, int i, int j,vector<vector<bool> > &flag, int match_index) { if(match_index == word.size()) return true; //true means used flag[i][j] = true; bool ans; //up if(i!=0 && board[i-1][j] == word[match_index] && flag[i-1][j] == false) { ans = find(board,word,i-1,j,flag,match_index + 1); if(ans) return true; } //right if(j!= board[0].size() - 1 && board[i][j+1] == word[match_index] && flag[i][j+1] == false) { ans = find(board,word,i,j+1,flag,match_index + 1); if(ans) return true; } //down if(i!= board.size() - 1 && board[i+1][j] == word[match_index] && flag[i+1][j] == false) { ans = find(board,word,i+1,j,flag,match_index + 1); if(ans) return true; } //left if(j!=0 && board[i][j-1] == word[match_index] && flag[i][j-1] == false) { ans = find(board,word,i,j-1,flag,match_index + 1); if(ans) return true; } flag[i][j] = false; return false; } };