【剑指Offer刷题】JZ12矩阵中的路径（中等）

目录

• 描述
• 思路
• 代码

描述

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如:
[ a b c e s f c s a d e e ] \\begin{bmatrix} a & b & c & e \\\\ s & f & c & s \\\\ a & d & e & e \\\\ \\end{bmatrix} ​asa​bfd​cce​ese​ ​
矩阵中包含一条字符串 “bcced” 的路径，但是矩阵中不包含 “abcb” 路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

数据范围：0 ≤ n, m ≤20 ,1 ≤ len ≤ 25

示例1

输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],\"abcced\"返回值：true

示例2

输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],\"abcb\"返回值：false

思路

本题是存在性问题，只要找到一条路径即可返回 true，使用深度优先搜索。

起点为字符串第一个字符，所以需要先找到起点，再从起点搜索：

int n = matrix.size(), m = matrix[0].size();// 先在矩阵中找到起点for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (matrix[i][j] == word[0]) { // ...// 深度优先搜索if (dfs()) return true;// ... } }}return false; // 未找到路径

本题 dfs() 需要哪些参数呢？

• 矩阵。
• 因为路径经过的位置不能再访问，所以需要传入 is_visited 数组记录已访问位置。
• 需要传入字符串和最后访问的字符串的位置。
• 需要传入在当前矩阵中的位置。

当字符串所有元素都在路径中时，返回 true。

bool dfs(vector<vector<char> >& matrix, vector<vector<bool> >& is_visited, string word, int idx, int xcur, int ycur);

下面是过程图，橙色表示当前位置，蓝色表示已访问位置，黑色箭头指向下一个满足条件的位置。

其实已经找到一条路径了，可以返回 true 了，但是如果没有找到，需要继续找路径的起点，进行dfs。

代码

#include using namespace std;class Solution {public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix char字符型vector<vector> * @param word string字符串 * @return bool布尔型 */ bool hasPath(vector<vector<char> >& matrix, string word) { // 深度优先搜索 int n = matrix.size(), m = matrix[0].size(); vector<vector<bool> > is_visited(n, vector<bool>(m, false)); // 先在矩阵中找到起点 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (matrix[i][j] == word[0]) {  for (int k = 0; k < n; ++k) fill(is_visited[k].begin(), is_visited[k].end(), false); // 清零，不会重新分配空间  // is_visited.assign(n, vector(m, false)); // 清零用assign()，会重新分配空间并初始化  // is_visited.resize(n, vector(m, false)); // 为什么没有清0：当容器大小不变时，resize不会有作用  // for (const auto& v : is_visited) {  // for (const auto& n : v) cout << n << \" \";  // cout << endl;  // }  // cout << endl;  is_visited[i][j] = true;  if (dfs(matrix, is_visited, word, 0, i, j)) { return true; // 找到路径  } } } } return false; // 未找到路径 } const vector<pair<int, int>> direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右 bool dfs(vector<vector<char> >& matrix, vector<vector<bool> >& is_visited, string word, int idx, int xcur, int ycur) { // cout << \"xcur:\" << xcur << \"\\tycur: \" << ycur << endl; // for (const auto& v : is_visited) { // for (const auto& n : v) cout << n << \" \"; // cout << endl; // } // cout << endl; if (idx >= word.size() - 1) return true; // 已经找到一条路径，快速返回 for (const auto& p : direct) { // 向四个方向搜索 int xnext = xcur + p.first; int ynext = ycur + p.second; if (xnext < 0 || ynext < 0 || xnext >= matrix.size() || ynext >= matrix[0].size()) continue; // 越界 if (!is_visited[xnext][ynext]) {// 如果还未访问 if (matrix[xnext][ynext] == word[idx + 1]) {// 如果是字符串下一个字符  is_visited[xnext][ynext] = true;  if (dfs(matrix, is_visited, word, idx + 1, xnext, ynext)) { return true; // 快速返回  }  is_visited[xnext][ynext] = false; // 回溯 } } } return false; // 返回继续搜索 }};int main() { Solution s; vector<vector<char>> matrix = { {\'A\',\'B\',\'C\',\'E\',\'H\',\'J\',\'I\',\'G\'}, {\'S\',\'F\',\'C\',\'S\',\'L\',\'O\',\'P\',\'Q\'}, {\'A\',\'D\',\'E\',\'E\',\'M\',\'N\',\'O\',\'E\'}, {\'A\',\'D\',\'I\',\'D\',\'E\',\'J\',\'F\',\'M\'}, {\'V\',\'C\',\'E\',\'I\',\'F\',\'G\',\'G\',\'S\'} }; string word = \"SGGFIECVAASABCEHJIGQEM\"; bool ret = s.hasPath(matrix, word); cout << ret << endl; return 0;}