Bulma en uzun <a href="https://leetcode.com/problems/longest-increasing-path-in-a-matrix/" rel="nofollow">https://leetcode.com/problems/longest-increasing-path-in-a-matrix/</a></p> <p>neden DFS kullanarak sonuç alamayan, bir matris

Question

Bu çevrimiçi yargıç olduğu yolu artan?

Her hücreden kaçarken, ya dört yöne geçin: sola, sağa, yukarı ya da aşağı.

En uzun yolun uzunluğunu saklayın.

/* 

for each elem, neighbours dfs 

*/ 
class Solution { 
public: 
    int longestIncreasingPath(vector<vector<int>>& matrix) { 
     int row = matrix.size(); 
     int col = matrix[0].size(); 
     int x[] = {0,1,0,-1};// l-r  -1,1  
     int y[] = {1,0,-1,0};// up-down +1,-1 
     int maxlen = 0; 

     for(int i = 0; i < row; i++){ 
      for(int j = 0; j< col; j++){ 
       // each node in the matrix[i][j], neighbours 
       int len = 0; 
       dfs(maxlen, len, i, j, x, y, matrix); 
      } 
     } 
     return maxlen; 
    } 

private: 
    bool isIn(int x, int y, int row, int col){ 
     if(x>=0&&x<=col && y>=0&&y<=row) return true; 
     else return false; 
    } 

    void dfs(int& maxlen, int len, int i, int j,int* x, int* y, vector<vector<int>> matrix){ 
     int row = matrix.size(); 
     int col = matrix[0].size(); 

     for(int k = 0; k < 4; k++){ 
      int i_t = i+x[k];//the current position 
      int j_t = j+y[k]; 
      if(isIn(i_t,j_t,row,col)&& (matrix[i_t][j_t]>matrix[i][j])){ // if inside the matrix, within the boundary&& the value of (i_t,j_t)> 
       len+=1; 
       maxlen = max(len,maxlen); 
       dfs(maxlen, len, i_t, j_t, x, y, matrix); 
      } 
     } 
    } 
}; 

Answer 1

Bu kodda birden çok sorun var.

1. if(x>=0&&x<=col && y>=0&&y<=row)
   if(x>=0&&x<col && y>=0&&y<row)

2. Bir yanlış cevap sonucu birlikte bir öğeden kaynaklanan tüm yolu ekliyoruz şekilde değiştirilmelidir. kodu

   len+=1; 
   maxlen = max(len,maxlen); 
   dfs(maxlen, len, i_t, j_t, x, y, matrix); 
   

   bu bölümü şekilde değiştirilmelidir: Birlikte farklı yönlere tüm yolları katmayan böylece

   //len+=1; 
   maxlen = max(len+1,maxlen); 
   dfs(maxlen, len+1, i_t, j_t, x, y, matrix); 
   

   .

   3. Çok fazla çakışan sorun çözüyorsunuz. dfs(r,c)'u aradığınızda sonucunu kaydedebilir ve bu değeri (dinamik programlama) için kullanabilirsiniz.

Bu bunu uygulayan şekli şöyledir:

#include <vector> 
#include <iostream> 
#include <map> 
using namespace std; 

map< pair<int,int>, int > dp; 
pair<int,int> moves[] = {{0,1},{0,-1},{1,0},{-1,0}}; 
vector<vector<int> > matrix = { {3,4,5}, 
           {3,2,6}, 
           {2,2,1}}; 

int dfs(int r, int c, int n_rows, int n_cols){ 
    pair<int,int> p = make_pair(r,c); 
    if (dp.count(p)){ 
     return dp[p]; 
    } 
    int mx = 0; 
    for (int i=0; i<4; ++i){ 
     int next_r = r+moves[i].first; 
     int next_c = c+moves[i].second; 
     if (0<=next_r && next_r < n_rows && 0<=next_c && next_c < n_cols){ 
      if (matrix[next_r][next_c] > matrix[r][c]) 
       mx = max(mx, dfs(next_r, next_c, n_rows, n_cols)); 
     } 
    } 
    mx++; 
    dp[p] = mx; 
    return mx; 
} 

int main(){ 
    int rows = matrix.size(); 
    int cols = matrix[0].size(); 
    int result = 0; 
    for (int i=0; i<rows; ++i){ 
     for (int j=0; j<cols; ++j){ 
      result = max(result, dfs(i,j,rows,cols)); 
     } 
    } 
    cout << result << endl;          
}