給定一個?m x n?二維字符網格?board?和一個字符串單詞?word?。如果?word?存在于網格中，返回?true?；否則，返回?false?。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。

思路一：回溯

bool sub_exist(char** board, int row, int col, char* word, int y, int x){if(*word == '\0')  return true;if(y < 0 || y >= row || x < 0 || x >= col || *word != board[y][x]return false;board[y][x] = '\0';  bool result = sub_exist(board, row, col, word + 1, y + 1, x) ||sub_exist(board, row, col, word + 1, y - 1, x) ||sub_exist(board, row, col, word + 1, y, x + 1) ||sub_exist(board, row, col, word + 1, y, x - 1) ;board[y][x] = *word;        return result;
}bool exist(char** board, int boardSize, int* boardColSize, char* word){for(int y = 0; y < boardSize; y ++){for(int x = 0; x < boardColSize[0]; x ++){if(board[y][x] == word[0] && sub_exist(board, boardSize, boardColSize[0], word, y, x))return true;}}return false;         
}

分析：

本題問字符串是否在字符網中，可使用回溯算法，判斷每一個字母前后左右是否有下一個字符，若沒有或者到達邊界即返回false，不斷遞歸判斷是否有匹配字符最后返回true或false

總結：

本題考察回溯算法的應用，注意遞歸的方向有前后左右四個方向。