题解 | #矩阵最长递增路径#
矩阵最长递增路径
https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2
#include <cstring> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 递增路径的最大长度 * @param matrix int整型vector<vector<>> 描述矩阵的每个数 * @return int整型 */ int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; bool isvalid(vector<vector<int> >& matrix,int x,int y,vector<vector<int> >& map) { return x>=0&&x<matrix.size()&&y>=0&&y<matrix[0].size()&&(map[x][y]==0); } void perution(vector<vector<int> >& matrix,int x,int y,vector<vector<int> >& map,int now,int& max){ if(map[x][y]!=0) return; map[x][y]=1;//visit if(now>max) max=now; for(int i=0;i<4;i++){ int x1=x+dx[i]; int y1=y+dy[i]; if(isvalid(matrix, x1, y1, map)&&matrix[x1][y1]>matrix[x][y]){ perution(matrix, x1, y1, map, now+1, max); } } map[x][y]=0; } int solve(vector<vector<int> >& matrix) { // write code here int num=0; int n=matrix.size(); int m=matrix[0].size(); vector<vector<int> > vis(n,vector<int>(m)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { perution(matrix,i,j,vis,1,num); } return num; } };
完完整整自己写的,DFS太奇妙了