Advertisement
SuitNdtie

POL

May 2nd, 2019
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<stack>
  4. using namespace std;
  5.  
  6. struct elem{
  7.     int val;
  8.     int I,J;
  9. };
  10.  
  11. bool mycmp(elem a,elem b){
  12.     return a.val < b.val;
  13. }
  14. int main()
  15. {
  16.     int n,m;
  17.     scanf("%d %d",&n,&m);
  18.     int table[n][m];
  19.     bool visited[n][m];
  20.     elem order[n*m];
  21.     int idx = 0;
  22.     for(int i = 0 ; i < n ; i ++){
  23.         for(int j = 0 ; j < m ; j ++){
  24.             scanf("%d",&table[i][j]);
  25.             visited[i][j] = false;
  26.             order[idx++] = {table[i][j],i,j};
  27.         }
  28.     }
  29.     sort(order,order+(n*m),mycmp);
  30.     int ans = 0;
  31.     for(int i = 0 ; i < idx ; i ++){
  32.         int val = order[i].val;
  33.         int I = order[i].I;
  34.         int J = order[i].J;
  35.         if(visited[I][J])continue;
  36.        
  37.         stack<elem> st;
  38.         st.push({table[I][J],I,J});
  39.         int cnt = 0;
  40.         int moveI[4] = {-1,0,1,0};
  41.         int moveJ[4] = {0,1,0,-1};
  42.     //  printf("Start (%d,%d) \n ",i,j);
  43.         while(!st.empty()){
  44.             int uv = st.top().val;
  45.             int ui = st.top().I;
  46.             int uj = st.top().J;
  47.         //  printf("Go to (%d,%d) : %d \n",ui,uj,uv);
  48.             if(visited[ui][uj])continue;
  49.             visited[ui][uj] = true;
  50.             st.pop();
  51.             cnt ++;
  52.             for(int k = 0 ; k < 4 ; k ++){
  53.                 int vi = ui + moveI[k];
  54.                 int vj = uj + moveJ[k];
  55.                 if(0 <= vi && vi < n && 0 <= vj && vj < m && table[vi][vj] - table[ui][uj] == 1){
  56.                     st.push({table[vi][vj],vi,vj});
  57.                 }
  58.             }
  59.         }
  60.         if(cnt > ans)ans = cnt;
  61.     }
  62.     printf("%d",ans);
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement