算法：矩阵中的路径 _矩阵

题目：

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

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

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

文章插图

示例：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

思路：
回溯思想
申明以下递归函数，含义：m*n的board，从位置[i][j]开始，能否找到单词word，变量visted标记找到的字母。

bool check(vector<vector<char>>& board, int m, int n, int i, int j, vector<vector<bool>>& visited, string word)

主函数中，尝试每次从举证不同的位置作为起始位置，调用上面申明的check函数，判断从该位置出发，能否找到单词。

代码：

class Solution {public:vector<int> dir = {-1,0, 1};bool valid(int m, int n, int i, int j){if(i>=0 && i<m && j>=0 && j<n)return true;elsereturn false;}bool check(vector<vector<char>>& board, int m, int n, int i, int j,vector<vector<bool>>& visited, string word){if(board[i][j] != word[0])return false;visited[i][j]=true;string s=word.substr(1, word.size()-1);if(s.size() == 0 )return true;for(auto& p: dir){for(auto& q: dir){if(abs(p)==1 && abs(q)==1)continue;if(valid(m,n,i+p,j+q) && !visited[i+p][j+q]){bool ret = check(board,m,n,i+p,j+q, visited, s);if(ret)return true;}}}visited[i][j]=false;return false;}bool exist(vector<vector<char>>& board, string word) {if(word.size() == 0)return false;int m=board.size();int n=board[0].size();vector<vector<bool>> visited;visited.resize(m);for(int i=0; i<m; i++)visited[i].resize(n);for(int i=0; i<m; i++){for(int j=0; j<n; j++){bool ret = check(board,m,n,i,j,visited,word);if(ret)return true;}}return false;}};

【算法：矩阵中的路径】