剑指offer——矩阵中的路径

网上说回溯法解决问题时，很多都是用dfs，通过dfs获得每一个结果子集，然后判断是否符合问题的解，如果不符合则回溯到上一层结果子集

class TreeNode { int val; TreeNode *children; TreeNode(int x):val(x), children(nullptr) {}; }; // dfs模板,这里只给出遍历多叉树的模板 map<int, int> visited; void dfs(TreeNode *root) { if (root == nullptr) { return; } if (visited.count(root->val)) { return; } visited(root->val) = 1; for (int i = 0; i < root->children.size(); ++i) { dfs(root->children[i]); } return; }

然而，我不知道回溯的模板是不是可以简化出来一个比较通用的模板，也许后面按照练习回溯专题的题时，可以总结出来一个通用模板。现在先把这道题解决:

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如：

矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

class Solution { public: int rows, cols; bool exit(vector<vector<char>> board, string word) { rows = board.size(); cols = board[0].size(); if (rows < 1 || cols < 1) return false; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (dfs(r, c, board, word, 0)) { return true; } } } return false; } bool dfs(int row, int col, vcetor<vector<char>> &board, string &word, int k) { if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != word[k]) { return false; } char tmp = board[row][col]; if (tmp = '#') { return false; } if (k = word.size() - 1 && board[row][col] == word[k]) return true; board[row][col] = '#'; bool res = dfs(row + 1, col, board, word, k+1) || dfs(row, col-1, board, word, k+1) || dfs(row - 1, col, board, word, k+1) || dfs(row, col+1, board, word, k+1); board[row][col] = tmp; return false; } }