fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define ii pair<int,int>
  5. #define F first
  6. #define S second
  7.  
  8.     int dx[4] = {1, 0, -1, 0};
  9.     int dy[4] = {0, -1, 0, 1};
  10.  
  11.     // Function to check if a cell has valid neighboring cells
  12.     bool check(vector<vector<int>>& matrix, ii it, int m, int n) {
  13.         for (int i = 0; i < 4; i++) {
  14.             if (it.F + dx[i] < 0 || it.F + dx[i] >= m || it.S + dy[i] < 0 || it.S + dy[i] >= n)
  15.                 continue;
  16.             if (matrix[it.F + dx[i]][it.S + dy[i]] > matrix[it.F][it.S]) return true;
  17.         }
  18.         return false;
  19.     }
  20.  
  21.     // Function to get the neighboring cells of a given cell
  22.     vector<ii> neighbours(vector<vector<int>>& matrix, ii it, int m, int n) {
  23.         vector<ii> neigh;
  24.         for (int i = 0; i < 4; i++) {
  25.             if (it.F + dx[i] < 0 || it.F + dx[i] >= m || it.S + dy[i] < 0 || it.S + dy[i] >= n)
  26.                 continue;
  27.             neigh.push_back({it.F + dx[i], it.S + dy[i]});
  28.         }
  29.         return neigh;
  30.     }
  31.  
  32.     // Memoization to avoid recalculating subproblems
  33.     vector<vector<int>> dp;
  34.  
  35.     int dfs(vector<vector<int>>& matrix, int m, int n, ii it) {
  36.         if (dp[it.F][it.S] != -1) return dp[it.F][it.S]; // Already computed
  37.  
  38.         int longest = 1;
  39.         for (auto v : neighbours(matrix, it, m, n)) {
  40.             if (matrix[v.F][v.S] > matrix[it.F][it.S]) {
  41.                 longest = max(longest, 1 + dfs(matrix, m, n, v));
  42.             }
  43.         }
  44.         return dp[it.F][it.S] = longest;
  45.     }
  46.  
  47.     int longestIncreasingPath(vector<vector<int>>& matrix) {
  48.         if (matrix.empty() || matrix[0].empty()) return 0;
  49.  
  50.         int m = matrix.size(), n = matrix[0].size();
  51.         dp = vector<vector<int>>(m, vector<int>(n, -1)); // Initialize dp table
  52.  
  53.         int result = 0;
  54.         for (int i = 0; i < m; i++) {
  55.             for (int j = 0; j < n; j++) {
  56.                 if (dp[i][j] == -1) { // If not visited
  57.                     result = max(result, dfs(matrix, m, n, {i, j}));
  58.                 }
  59.             }
  60.         }
  61.         return result;
  62.     }
  63.  
  64. int32_t main() {
  65.     int m, n; 
  66.     cin >> m >> n;
  67.     vector<vector<int>> matrix(m, vector<int>(n));
  68.     for (int i = 0; i < m; i++) {
  69.         for (int j = 0; j < n; j++) {
  70.             cin >> matrix[i][j];
  71.         }
  72.     }
  73.     cout << longestIncreasingPath(matrix) << endl;
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
3 5
9 9 8 7 6
6 6 8 4 5
2 1 1 2 3
stdout
copy 
8
https://ideone.com/eTOlT9
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!