Advertisement
radmickey

Untitled

Apr 15th, 2023
906
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int n, m;
  7. vector<vector<int>> matrix;
  8. vector<vector<int>> dp;
  9.  
  10. int dx[] = {-1, 0, 1, 0};
  11. int dy[] = {0, 1, 0, -1};
  12.  
  13. bool is_valid(int x, int y) {
  14.     return x >= 0 && x < n && y >= 0 && y < m;
  15. }
  16.  
  17. int dfs(int x, int y) {
  18.     if (dp[x][y] != 1) {
  19.         return dp[x][y];
  20.     }
  21.  
  22.     for (int i = 0; i < 4; i++) {
  23.         int nx = x + dx[i], ny = y + dy[i];
  24.         if (is_valid(nx, ny) && matrix[nx][ny] > matrix[x][y]) {
  25.             dp[x][y] = max(dp[x][y], 1 + dfs(nx, ny));
  26.         }
  27.     }
  28.     return dp[x][y];
  29. }
  30.  
  31. int main() {
  32.     cin >> n >> m;
  33.  
  34.     matrix.resize(n, vector<int>(m));
  35.     dp.resize(n, vector<int>(m, 1));
  36.  
  37.     for (int i = 0; i < n; i++) {
  38.         for (int j = 0; j < m; j++) {
  39.             cin >> matrix[i][j];
  40.         }
  41.     }
  42.  
  43.     int ans = 0;
  44.     for (int i = 0; i < n; i++) {
  45.         for (int j = 0; j < m; j++) {
  46.             ans = max(ans, dfs(i, j));
  47.         }
  48.     }
  49.  
  50.     cout << ans << '\n';
  51.  
  52.     return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement