Guest User

Untitled

a guest
Jul 11th, 2016
436
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define icin(x) scanf("%d",&x)
  4. #define pb push_back
  5. #define LL long long
  6. #define F first
  7. #define S second
  8. #define eps ((double)1e-8)
  9. #define maxn 109
  10. #define maxm 100009
  11.  
  12. using namespace std;
  13.  
  14. int a[maxn][maxn],b[maxn][maxn];
  15.  
  16.  int r,c;
  17.  bool valid(int i,int j)
  18.  {
  19.   if(i<1 || i>r)
  20.     return 0;
  21.   if(j<1 || j>c)
  22.     return 0;
  23.   return 1;
  24.  }
  25.  
  26. int main()
  27. {
  28.   int t;
  29.   icin(t);
  30.   int x =0;
  31.   while(t--)
  32.   {
  33.     x++;
  34.    
  35.     icin(r);icin(c);
  36.  
  37.     vector< pair<int,int> > vec[1001];
  38.     int vis[100][100];
  39.     memset(vis,0,sizeof(vis));
  40.     memset(b,0,sizeof(b));
  41.     for(int i=1;i<=r;i++)
  42.     {
  43.       for(int j=1;j<=c;j++)
  44.       {
  45.         icin(a[i][j]);
  46.         vec[a[i][j]].pb({i,j});
  47.       }
  48.     }
  49.     int ans =0;
  50.  
  51.     for(int num=1;num<=1000;num++)
  52.     {
  53.       if(num>1)
  54.       {
  55.         for(int i=0;i<vec[num-1].size();i++)
  56.         {
  57.           vis[vec[num-1][i].F][vec[num-1][i].S]=0;
  58.         }
  59.       }
  60.       for(int i=0;i<vec[num].size();i++)
  61.       {
  62.         int row = vec[num][i].F,col=vec[num][i].S;
  63.         vector< pair<int,int> > store;
  64.         queue< pair<int,int> > q;
  65.  
  66.         if(vis[row][col]==0)
  67.         {
  68.          
  69.           //cout << row << " " << col << endl;
  70.           int ch = 1234567;
  71.           store.pb({row,col});
  72.           q.push({row,col});
  73.           vis[row][col]=1;
  74.           while(!q.empty())
  75.           {
  76.             auto p = q.front();
  77.             q.pop();
  78.             int t1=p.F,t2=p.S;
  79.             if(valid(t1-1,t2))
  80.             {
  81.               if(a[t1-1][t2]==num && vis[t1-1][t2]==0)
  82.               {
  83.                 store.pb({t1-1,t2});
  84.                 vis[t1-1][t2]=1;
  85.                 q.push({t1-1,t2});
  86.               }
  87.               else if(a[t1-1][t2]!=num)
  88.                 ch = min(a[t1-1][t2],ch);
  89.             }
  90.             else
  91.               ch=0;
  92.             if(valid(t1+1,t2))
  93.             {
  94.               if(a[t1+1][t2]==num && vis[t1+1][t2]==0)
  95.               {
  96.                 store.pb({t1+1,t2});
  97.                 vis[t1+1][t2]=1;
  98.                 q.push({t1+1,t2});
  99.               }
  100.               else if(a[t1+1][t2]!=num)
  101.                 ch = min(a[t1+1][t2],ch);
  102.             }
  103.             else
  104.               ch=0;
  105.             if(valid(t1,t2-1))
  106.             {
  107.               if(a[t1][t2-1]==num && vis[t1][t2-1]==0)
  108.               {
  109.                 store.pb({t1,t2-1});
  110.                 vis[t1][t2-1]=1;
  111.                 q.push({t1,t2-1});
  112.               }
  113.               else if(a[t1][t2-1]!=num)
  114.                 ch = min(a[t1][t2-1],ch);
  115.             }
  116.             else
  117.               ch=0;
  118.             if(valid(t1,t2+1))
  119.             {
  120.               if(a[t1][t2+1]==num && vis[t1][t2+1]==0)
  121.               {
  122.                 store.pb({t1,t2+1});
  123.                 vis[t1][t2+1]=1;
  124.                 q.push({t1,t2+1});
  125.               }
  126.               else if(a[t1][t2+1]!=num)
  127.                 ch = min(a[t1][t2+1],ch);
  128.             }
  129.             else
  130.               ch=0;
  131.           }
  132.  
  133.      //   cout << num << " " << ch << endl;
  134.         if(ch<num || ch==1234567)
  135.           continue;
  136.         else
  137.         {
  138.           for(int j=0;j<store.size();j++)
  139.           {
  140.             ans +=  (ch - num);
  141.             a[store[j].F][store[j].S] = ch;
  142.             vec[ch].pb({store[j].F,store[j].S});
  143.            
  144.           }
  145.         }
  146.  
  147.         }
  148.    
  149.       }
  150.     }
  151.  
  152.     // for(int i=1;i<=r;i++)
  153.     // {
  154.     //   for(int j=1;j<=c;j++)
  155.     //     cout << a[i][j] << " ";
  156.     //   cout << endl;
  157.     // }
  158.  
  159.     cout << "Case #" << x << ": " << ans << endl;
  160.   }
  161. }
Add Comment
Please, Sign In to add comment