fork download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<vector>
  4. #include<queue>
  5. #include<tuple>
  6. using namespace std;
  7.  
  8. #define N 2010
  9. int n;
  10. char dir[N];
  11. const int dx[]={0, 0, -1, 1}, dy[]={-1, 1, 0, 0};
  12. int tugi[N*N], hno[N*N], s[N*N], op[N*N];
  13. bool vis[N*N];
  14. inline bool ingrid(int x, int y){
  15.     return 0<=x && x<=n-1 && 0<=y && y<=n-1;
  16. }
  17. inline int sc(int x, int y){
  18.     return x*n+y;
  19. }
  20. void dfs(int i){
  21.     if(s[i]) return;
  22.     s[i] = 1;
  23.     int x=i/n, y=i%n;
  24.     for(int j=0; j<=3; j++) if(ingrid(x+dx[j], y+dy[j])){
  25.         int ch = sc(x+dx[j], y+dy[j]);
  26.         if(tugi[ch] != i) continue;
  27.         dfs(ch);
  28.         if(s[i] < s[ch]+1){
  29.             op[i] = ch;
  30.             s[i] = s[ch]+1;
  31.         }
  32.     }
  33. }
  34.  
  35. int main(){
  36.     scanf("%d", &n);
  37.     for(int i=0; i<=n-1; i++){
  38.         scanf("%s", dir);
  39.         for(int j=0; j<=n-1; j++){
  40.             int k = -1;
  41.             switch(dir[j]){
  42.                 case 'l': k=0; break;
  43.                 case 'r': k=1; break;
  44.                 case 'u': k=2; break;
  45.                 case 'd': k=3; break;
  46.             }
  47.             if(ingrid(i+dx[k], j+dy[k])){
  48.                 tugi[sc(i, j)] = sc(i+dx[k], j+dy[k]);
  49.             }else{
  50.                 tugi[sc(i, j)] = sc(i, j);
  51.             }
  52.         }
  53.     }
  54.     vector<int> toubu;
  55.     for(int i=0; i<=n*n-1; i++) if(!vis[i]){
  56.         int usagi=i, kame=i;
  57.         bool loli = true;
  58.         do{
  59.             usagi = tugi[tugi[usagi]];
  60.             kame = tugi[kame];
  61.             if(vis[kame]){
  62.                 loli=false; break;
  63.             }
  64.         }while(usagi!=kame);
  65.         if(loli){
  66.             do{
  67.                 usagi = tugi[usagi];
  68.                 s[kame]++;
  69.             }while(usagi!=kame);
  70.             toubu.push_back(kame);
  71.         }
  72.         for(kame=i; !vis[kame]; kame=tugi[kame]){
  73.             vis[kame] = true;
  74.         }
  75.     }
  76.     memset(hno, -1, n*n*sizeof(int));
  77.     for(int i=0; i<(int)toubu.size(); i++){
  78.         for(int j=toubu[i]; hno[j]==-1; j=tugi[j]){
  79.             hno[j] = i;
  80.         }
  81.     }
  82.     memset(op, -1, n*n*sizeof(int));
  83.     for(int i=0; i<=n*n-1; i++) if(hno[i]==-1){
  84.         dfs(i);
  85.     }
  86.     for(int i=0; i<=n*n-1; i++) if(hno[i]==-1 && ~hno[tugi[i]]){
  87.         int h = toubu[hno[tugi[i]]];
  88.         if(op[h]==-1 || s[i]>s[op[h]]){
  89.             s[h] += s[i]-s[op[h]];
  90.             op[h] = i;
  91.         }
  92.     }
  93.     priority_queue<pair<int, int>> pq;
  94.     for(int i=0; i<(int)toubu.size(); i++){
  95.         pq.push(make_pair(s[toubu[i]], toubu[i]));
  96.     }
  97.     int ans = 0;
  98.     for(int c=1; !pq.empty(); c^=1){
  99.         int d, i;
  100.         tie(d, i) = pq.top(); pq.pop();
  101.         if(c) ans += d;
  102.         if(~hno[i]){
  103.             int j = i;
  104.             do{
  105.                 int x=j/n, y=j%n;
  106.                 for(int k=0; k<=3; k++) if(ingrid(x+dx[k], y+dy[k])){
  107.                     int ch = sc(x+dx[k], y+dy[k]);
  108.                     if(~hno[ch] || tugi[ch]!=j || ch==op[i]) continue;
  109.                     pq.push(make_pair(s[ch], ch));
  110.                 }
  111.                 j = tugi[j];
  112.             }while(j!=i);
  113.             if(op[i] == -1) continue;
  114.             i = op[i];
  115.         }
  116.         for(; ~op[i]; i=op[i]){
  117.             int x=i/n, y=i%n;
  118.             for(int j=0; j<=3; j++) if(ingrid(x+dx[j], y+dy[j])){
  119.                 int ch = sc(x+dx[j], y+dy[j]);
  120.                 if(tugi[ch]!=i || ch==op[i]) continue;
  121.                 pq.push(make_pair(s[ch], ch));
  122.             }
  123.         }
  124.     }
  125.     printf("%d\n", ans);
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout 0s 4164KB
comments (?)
stdin
copy 
6
drludl
rudlru
dldldl
rldlrd
uuudlr
ddlluu
stdout
copy 
19
https://ideone.com/H4nMwe
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!