题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
注意：
- 输入的路径不为空；
- 所有出现的字符均为大写英文字母；
数据范围
矩阵中元素的总个数 [0,900]。
路径字符串的总长度 [0,900]。
样例
matrix= [ ["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"] ] str="BCCE" , return "true" str="ASAE" , return "false"
方法一：DFS O(n23k)
这道题直接深搜，遍历每一个位置，只要有一个位置可以成功就返回 true 。这里要注意的是不能走回头路，需要判断当前走的位置之前是否已经走过。具体步骤如下：
遍历每一个位置，如果有一个位置递归后可以得到目标字符串则就算成功。
进入递归函数，用 dis 来记录当前在目标字符串中遍历到的位置，如果当前位置的字符与矩阵中遍历到字符不同，就直接返回 false 。
如果 dis = str.size() - 1 ，说明已经匹配成功了，返回 true 。
如果流程 2 和 3 都没有被返回的话，就进行正常的递归操作，每次递归都回往上下左右四个方向走，如果满足条件就进入下一次递归操作。注意，用 -1 来表示该位置已经被遍历过，并且递归完要记得恢复之前的数值。
只要匹配成功一次，主函数就直接返回 true 。
class Solution { public: int n, m; int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 }; bool dfs(vector<vector<char>>& matrix, int x, int y, int dis, string str) { //如果不相等，直接返回false if (matrix[x][y] != str[dis]) return false; //判断字符串指针是否已经走到最后 if (dis == str.size() - 1) return true; char c = matrix[x][y]; //备份数组元素 matrix[x][y] = -1; //标记当前位置已经走过 for (int i = 0; i < 4; i++) { int mx = x + dx[i], my = y + dy[i]; //如果不满足要求则直接跳过接下来的步骤 if (mx < 0 || mx >= n || my < 0 || my >= m || matrix[mx][my] == -1) continue; if (dfs(matrix, mx, my, dis + 1, str)) return true; } matrix[x][y] = c; //恢复数组元素 return false; } bool hasPath(vector<vector<char>>& matrix, string& str) { if (matrix.size() == 0 || matrix[0].size() == 0) return false; n = matrix.size(), m = matrix[0].size(); //遍历每一个位置 for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (dfs(matrix, i, j, 0, str)) return true; return false; } };
欢迎大家在评论区交流~
