Guest User

Untitled

a guest
Nov 24th, 2017
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1.  
  2. #include <cstdlib>
  3. #include <fstream>
  4. #include <vector>
  5. #include <cstring>
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <queue>
  11. using namespace std;
  12.  
  13. char pch[51][51];
  14. int pole[51][51];
  15. bool vis[51][51], vis1[50][50];
  16. int ocnt[1000];
  17. int p1[4] = { 1, -1, 0, 0 };
  18. int p2[4] = { 0, 0, 1, -1 };
  19. int o1[8] = { 1, -1, 0, 0, -1, -1, 1, 1};
  20. int o2[8] = { 0, 0, 1, -1, 1, -1, 1, -1};
  21. int x_max, y_max, ostr=1, last, st;
  22. bool gets_out = false;
  23. int res[1000], fin[1000];
  24.  
  25. bool out (int x, int y)
  26. {
  27.     vis[x][y] = true;
  28.     for (int i=0; i<4; i++)
  29.     {
  30.         if (x == x_max-1 || x == 0 || y == y_max-1 || y == 0)
  31.             return true;
  32.         if (pole[x+p1[i]][y+p2[i]] == 0 && !vis[x+p1[i]][y+p2[i]])
  33.         {
  34.             if (out(x+p1[i], y+p2[i]))
  35.                 return true;
  36.         }
  37.         else
  38.         {
  39.             if (!vis[x+p1[i]][y+p2[i]] && pole[x+p1[i]][y+p2[i]] != st )
  40.             {
  41.                 ocnt[pole[x+p1[i]][y+p2[i]]]++;
  42.                 vis[x+p1[i]][y+p2[i]] = true;          
  43.             }
  44.         }
  45.     }
  46.     return false;
  47. }
  48.  
  49. void dfs (int x, int y, int c)
  50. {
  51.     if (c==0) vis1[x][y] = true;
  52.     vis[x][y] = true;
  53.     if (c>0)
  54.         pole[x][y] = c;
  55.     else
  56.     {
  57.         if (out (x, y))
  58.             gets_out = true;
  59.     }
  60.  
  61.     for (int i=0; i<8; i++)
  62.         if (pch[x+o1[i]][y+o2[i]] == 'x' && !vis[x+o1[i]][y+o2[i]])
  63.             dfs(x+o1[i], y+o2[i], c);
  64. }
  65.        
  66. int cnt(int x)
  67. {
  68.     int k = 0;
  69.     int p = 0;
  70.     for (int i=1; i<ostr; i++)
  71.     {
  72.         if (res[i] == x)
  73.         {
  74.             k=cnt(i)+1;
  75.             if (k>p)
  76.                 p=k;
  77.         }
  78.     }
  79.  
  80.     fin[p]++;
  81.     return p;
  82. }
  83. int main()
  84. {
  85.     int m;
  86.     cin >> x_max >> y_max;
  87.  
  88.     for (int i=0; i<x_max; i++)
  89.         for (int j=0; j<y_max; j++)
  90.             cin >> pch[i][j];
  91.  
  92.     memset(pole,0,sizeof(pole));
  93.     memset(vis,false,sizeof(vis));
  94.     memset(fin,0,sizeof(fin));
  95.  
  96.     for (int i=0; i<x_max; i++)
  97.         for (int j=0; j<y_max; j++)
  98.             if (pch[i][j]=='x' && !vis[i][j])
  99.             {
  100.                 dfs(i,j,ostr);
  101.                 ostr++;
  102.             }
  103.  
  104.     memset(vis,false,sizeof(vis));
  105.     memset(vis1,false,sizeof(vis1));
  106.     for (int i=0; i<x_max; i++)
  107.         for (int j=0; j<y_max; j++)
  108.         {
  109.             if (pole[i][j]>0 && !vis[i][j] && !vis1[i][j])
  110.             {
  111.                 dfs(i,j,0);
  112.                 if (gets_out)
  113.                     res[pole[i][j]] = 0;
  114.                 else
  115.                 {
  116.                     int bg=0,bgi;
  117.                     for (int d=1; d<ostr; d++)
  118.                     {
  119.                         if (ocnt[d]>bg)
  120.                         {
  121.                             bg=ocnt[d];
  122.                             bgi=d;
  123.                         }
  124.                     }
  125.                     res[pole[i][j]] = bgi;
  126.                 }
  127.                 memset(vis,false,sizeof(vis));
  128.                 memset(ocnt, 0, sizeof(ocnt));
  129.                 gets_out=false;
  130.             }
  131.         }
  132.    
  133.     for (int i=1; i<ostr; i++)
  134.     {
  135.         if (res[i]==0)
  136.             m=cnt(i);
  137.     }
  138.  
  139.     int z=0;
  140.     while (fin[z]>0)
  141.     {
  142.         cout << fin[z] << endl;
  143.         z++;
  144.     }
  145.     return 0;
  146. }
Add Comment
Please, Sign In to add comment