Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <fstream>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- #include <queue>
- using namespace std;
- char pch[51][51];
- int pole[51][51];
- bool vis[51][51], vis1[50][50];
- int ocnt[1000];
- int p1[4] = { 1, -1, 0, 0 };
- int p2[4] = { 0, 0, 1, -1 };
- int o1[8] = { 1, -1, 0, 0, -1, -1, 1, 1};
- int o2[8] = { 0, 0, 1, -1, 1, -1, 1, -1};
- int x_max, y_max, ostr=1, last, st;
- bool gets_out = false;
- int res[1000], fin[1000];
- bool out (int x, int y)
- {
- vis[x][y] = true;
- for (int i=0; i<4; i++)
- {
- if (x == x_max-1 || x == 0 || y == y_max-1 || y == 0)
- return true;
- if (pole[x+p1[i]][y+p2[i]] == 0 && !vis[x+p1[i]][y+p2[i]])
- {
- if (out(x+p1[i], y+p2[i]))
- return true;
- }
- else
- {
- if (!vis[x+p1[i]][y+p2[i]] && pole[x+p1[i]][y+p2[i]] != st )
- {
- ocnt[pole[x+p1[i]][y+p2[i]]]++;
- vis[x+p1[i]][y+p2[i]] = true;
- }
- }
- }
- return false;
- }
- void dfs (int x, int y, int c)
- {
- if (c==0) vis1[x][y] = true;
- vis[x][y] = true;
- if (c>0)
- pole[x][y] = c;
- else
- {
- if (out (x, y))
- gets_out = true;
- }
- for (int i=0; i<8; i++)
- if (pch[x+o1[i]][y+o2[i]] == 'x' && !vis[x+o1[i]][y+o2[i]])
- dfs(x+o1[i], y+o2[i], c);
- }
- int cnt(int x)
- {
- int k = 0;
- int p = 0;
- for (int i=1; i<ostr; i++)
- {
- if (res[i] == x)
- {
- k=cnt(i)+1;
- if (k>p)
- p=k;
- }
- }
- fin[p]++;
- return p;
- }
- int main()
- {
- int m;
- cin >> x_max >> y_max;
- for (int i=0; i<x_max; i++)
- for (int j=0; j<y_max; j++)
- cin >> pch[i][j];
- memset(pole,0,sizeof(pole));
- memset(vis,false,sizeof(vis));
- memset(fin,0,sizeof(fin));
- for (int i=0; i<x_max; i++)
- for (int j=0; j<y_max; j++)
- if (pch[i][j]=='x' && !vis[i][j])
- {
- dfs(i,j,ostr);
- ostr++;
- }
- memset(vis,false,sizeof(vis));
- memset(vis1,false,sizeof(vis1));
- for (int i=0; i<x_max; i++)
- for (int j=0; j<y_max; j++)
- {
- if (pole[i][j]>0 && !vis[i][j] && !vis1[i][j])
- {
- dfs(i,j,0);
- if (gets_out)
- res[pole[i][j]] = 0;
- else
- {
- int bg=0,bgi;
- for (int d=1; d<ostr; d++)
- {
- if (ocnt[d]>bg)
- {
- bg=ocnt[d];
- bgi=d;
- }
- }
- res[pole[i][j]] = bgi;
- }
- memset(vis,false,sizeof(vis));
- memset(ocnt, 0, sizeof(ocnt));
- gets_out=false;
- }
- }
- for (int i=1; i<ostr; i++)
- {
- if (res[i]==0)
- m=cnt(i);
- }
- int z=0;
- while (fin[z]>0)
- {
- cout << fin[z] << endl;
- z++;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment