【需要理解】80 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

题解1 回溯（需要改变起点）

class Solution {bool res = false;int ls, cs;
public:void backtrace(vector<vector<char>>& board, string& word, int r, int c, int p){// 顺序很重要, 养成习惯，先判断return条件，再排除其他if(p == word.size()){res = true;return;}// 边界if(r >= ls || c >= cs || r < 0 || c < 0 || res) return;// 有一个错误字符直接return换下一种组合/该字符起点不对需要换if(board[r][c] != word[p]) return;// 相当于 used/visited——// 此题条件下，往左往上往下往右可能会重复选很多格子，但是当前格子不允许重复选board[r][c] = (char)(-board[r][c]);// 水平 （左右）backtrace(board, word, r, c+1, p+1);backtrace(board, word, r, c-1, p+1);// 垂直  (上下)backtrace(board, word, r+1, c, p+1);backtrace(board, word, r-1, c, p+1);// 撤回操作（走不通，需要换起点）// backtrace结束后会到下一个出发点，若(r, c)是中途格子，需要复位board[r][c] = (char)(-board[r][c]);}bool exist(vector<vector<char>>& board, string word) {ls = board.size();cs = board[0].size();// 遍历搜索起点for(int i = 0; i < ls; i++){for(int j = 0; j < cs; j++){// 搜索起点改变if(board[i][j] == word[0])backtrace(board, word, i, j, 0);if(res) return true;}}return res;}
};