ccbeginner

UVa Q10285

Jan 23rd, 2020
102
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10285
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int n,m;
  6. int arr[100][100];
  7. bool vis[100][100];
  8. int stp[100][100];
  9.  
  10. int dx[] = {0,1,0,-1};
  11. int dy[] = {1,0,-1,0};
  12. int ans;
  13.  
  14. int dfs(int x, int y){
  15.     if(stp[x][y] != 0)return stp[x][y];
  16.     int ret = 0;
  17.     vis[x][y] = 1;
  18.     for(int i = 0; i < 4; ++i){
  19.         int nx = x+dx[i], ny = y+dy[i];
  20.         if(0 <= nx && nx < n && 0 <= ny && ny < m && !vis[nx][ny] && arr[x][y] > arr[nx][ny]){
  21.             ret = max(ret, dfs(nx, ny));
  22.         }
  23.     }
  24.     vis[x][y] = 0;
  25.     stp[x][y] = ret+1;
  26.     return stp[x][y];
  27. }
  28.  
  29. int32_t main(){
  30.     string s;
  31.     int t;
  32.     cin >> t;
  33.     while(t--){
  34.         memset(stp, 0, sizeof(stp));
  35.         cin >> s >> n >> m;
  36.         ans = 0;
  37.         for(int i = 0; i < n; ++i){
  38.             for(int j = 0; j < m; ++j){
  39.                 cin >> arr[i][j];
  40.             }
  41.         }
  42.         for(int i = 0; i < n; ++i){
  43.             for(int j = 0; j < m; ++j){
  44.                 ans = max(ans, dfs(i,j));
  45.             }
  46.         }
  47.         cout << s << ": " << ans << '\n';
  48.     }
  49.     return 0 ;
  50. }
RAW Paste Data