Advertisement
Guest User

Untitled

a guest
Feb 20th, 2018
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. using namespace std;
  4.  
  5. int map[501][501];
  6. int dp[501][501];
  7. int ans=1;
  8. int n;
  9. int dy[] = { -1, 1 , 0 ,0 };
  10. int dx[] = { 0,0,1,-1 };
  11.  
  12.  
  13. int dfs(int y, int x ) {
  14.     for (int i = 0; i < 4; i++) {
  15.         int ny, nx;
  16.         ny = y + dy[i];
  17.         nx = x + dx[i];
  18.  
  19.         if (ny < 0 || nx < 0 || ny >= n || nx >= n || map[ny][nx] <= map[y][x]) continue;
  20.  
  21.         if (dp[ny][nx] > 1) {
  22.             if (dp[y][x] < dp[ny][nx] + 1) {
  23.                 dp[y][x] = dp[ny][nx] + 1;
  24.             }
  25.         }
  26.         else {
  27.             int cnt = dfs(ny, nx);
  28.             if (cnt > dp[y][x]) {
  29.                 dp[y][x] = cnt;
  30.             }
  31.         }
  32.     }
  33.     return dp[y][x] + 1;
  34.  
  35. }
  36.  
  37. int main() {
  38.    
  39.     int k;
  40.  
  41.     scanf_s("%d", &n);
  42.     for (int i = 0; i < n; i++) {
  43.         for (int j = 0; j < n; j++) {
  44.             scanf_s("%d",&map[i][j]);
  45.             dp[i][j] = 1;
  46.         }
  47.     }
  48.  
  49.     for (int i = 0; i < n; i++) {
  50.         for (int j = 0; j < n; j++) {
  51.             if (dp[i][j] == 1 ) {
  52.                 k = dfs(i, j) -1;
  53.                 if (k > ans) {
  54.                     ans = k;
  55.                 }
  56.             }
  57.            
  58.         }
  59.     }
  60.  
  61.     printf_s("%d", ans);
  62.  
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement