题解 | #矩阵中的路径#
矩阵中的路径
https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6
#include <string> #include <type_traits> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix char字符型vector<vector<>> * @param word string字符串 * @return bool布尔型 */ //判断该格子经历次数(只能经历一次) int flag[25][25]={0}; int dxy[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; bool find(vector<vector<char> >& matrix,int n,int x,int y,string word,string temp) { // if(x>=matrix.size()||x<0||y>=matrix[0].size()||y<0||matrix[x][y]!=word[n]) // { // return; // } if(n>=word.size()-1&&temp==word) { return true; } bool res; for(int i=0;i<=3;i++) { x=x+dxy[i][0]; y=y+dxy[i][1]; if(flag[x][y]==0&&!(x>=matrix.size()||x<0||y>=matrix[0].size()||y<0)){ flag[x][y]=1; temp=temp+matrix[x][y]; if(matrix[x][y]==word[n+1])res=find(matrix,n+1,x,y,word,temp); temp.pop_back(); flag[x][y]=0; } x=x-dxy[i][0]; y=y-dxy[i][1]; } return res; } bool hasPath(vector<vector<char> >& matrix, string word) { // write code here string temp; for(int i=0;i<matrix.size();i++){ for(int j=0;j<matrix[0].size();j++){ if(matrix[i][j]==word[0]) { flag[i][j]=true; temp.push_back(word[0]); if(find(matrix,0,i,j,word,temp)) return true; temp.pop_back(); flag[i][j]=false; } } } return false; } };