题解 | #矩阵中的路径#
矩阵中的路径
https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6
#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix char字符型vector<vector<>> * @param word string字符串 * @return bool布尔型 */ bool dfs(vector<vector<char>>& matrix, int n, int m, int i, int j, string word, int k, vector<vector<bool>>& flag){ if (i<0||i>=n||j<0||j>=m||(matrix[i][j]!=word[k]||flag[i][j]==true)) { return false; } if (k==word.length()-1) { return true; } flag[i][j] = true; if(dfs(matrix, n, m, i-1, j, word, k+1, flag)|| dfs(matrix, n, m, i+1, j, word, k+1, flag)|| dfs(matrix, n, m, i, j-1, word, k+1, flag)|| dfs(matrix, n, m, i, j+1, word, k+1, flag)){ return true; } flag[i][j] = false; return false; } bool hasPath(vector<vector<char> >& matrix, string word) { // write code here if (matrix.size()==0) { return false; } int n = matrix.size(); int m = matrix[0].size(); vector<vector <bool>> flag(n, vector<bool>(m, false)); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if(dfs(matrix, n, m, i, j, word, 0, flag)){ return true; } } } return false; } };
为了在n*m矩阵matrix中判断是否存在一条路径包括指定的字符串string word, 考虑使用递归的思想,即把问题分解为寻找下一个子字符串。具体而言,当判断当前节点为字符串中特定位置的字符时,则开始判断其上下左右的字符是否为字符串中的下一个字符,,依次递归。