Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <cstring>
- #include <vector>
- #include <set>
- #include <algorithm>
- #include <fstream>
- using namespace std;
- int n, m;
- char arr[101][101];
- int mat[101][101];
- bool visited[101][101];
- const int di[] = {-1, 1, 0, 0, -1, -1, 1, 1};
- const int dj[] = {0, 0, -1, 1, 1, -1, -1, 1};
- int ii, jj, ni, nj;
- // -1 - padding
- //0 - dots(free places)
- //from 1 to X - islands
- void markIslands(int &i, int &j, int &mark){
- queue<int> q;
- q.push(i);
- q.push(j);
- mat[i][j] = mark;
- // memset(visited, false, sizeof visited);
- while(!q.empty()) {
- ii = q.front();
- q.pop();
- jj = q.front();
- q.pop();
- for(int k = 0; k < 8; k ++){
- ni = di[k] + ii;
- nj = dj[k] + jj;
- if(ni < 0 || nj < 0 || ni > n || nj > m)continue;
- if(visited[ni][nj])continue;
- if(mat[ni][nj] == 0)continue;
- if(mat[ni][nj] == -1)continue;
- q.push(ni);
- q.push(nj);
- visited[ni][nj] = true;
- mat[ni][nj] = mark;
- }
- }
- }
- bool canLeave(int &i, int &j, int &mark, int &currMark){
- queue<int> q;
- q.push(i);
- q.push(j);
- //memset(visited, false, sizeof visited);
- int E;
- visited[i][j] = true;
- while(!q.empty()){
- ii = q.front();
- q.pop();
- jj = q.front();
- q.pop();
- if(mat[ii][jj] == -1){
- return true;
- }
- if(mat[ii][jj] == 0){
- E = 4;
- }
- else{
- E = 8;
- }
- for(int k = 0; k < E; k ++){
- ni = di[k] + ii;
- nj = dj[k] + jj;
- if(ni < 0 || nj < 0 || ni > n || nj > m)continue;
- if(visited[ni][nj])continue;
- if(mat[ni][nj] == 0 || mat[ni][nj] == -1 || mat[ni][nj] != mark || mat[ni][nj] == currMark){
- q.push(ni);
- q.push(nj);
- visited[ni][nj] = true;
- }
- }
- }
- return false;
- }
- bool vis[101][101][701];
- vector<int> ret;
- int dfs(int &ii, int &jj, int &mark){
- if(vis[ii][jj][mark])return 0;
- vis[ii][jj][mark] = true;
- int E;
- if(mat[ii][jj] == 0){
- E = 4;
- }
- else{
- E = 8;
- }
- int ni, nj;
- int mxx = 0, tmp;
- int k;
- for( k =0; k < E; k ++){
- ni = di[k] + ii;
- nj = dj[k] + jj;
- if(ni < 0 || nj < 0 || ni > n || nj > m)continue;
- if(vis[ni][nj][mat[ni][nj]])continue;
- if(vis[ni][nj][mark])continue;
- if(mat[ni][nj] != -1 && mat[ni][nj] != 0){
- memset(visited, false, sizeof visited);
- if(mat[ni][nj] != mark && !canLeave(ni, nj, mark, mat[ni][nj])){
- tmp = dfs(ni, nj, mat[ni][nj]);
- mxx = max(mxx, tmp + 1);
- ret.push_back(tmp);
- // cout << tmp << endl;
- }
- else if(mat[ni][nj] == mark){
- mxx = max(dfs(ni, nj, mark), mxx);
- }
- else{
- }
- }
- else if(mat[ni][nj] == 0 && mat[ni][nj] != -1){
- mxx = max(dfs(ni, nj, mark), mxx);
- }
- }
- return mxx;
- }
- void printMat(){
- for(int i=0; i<= n; i ++){
- for(int j = 0; j <= m; j ++)
- {
- cout << mat[i][j] << " ";
- }
- cout << endl;
- }
- }
- int main(int argc, const char * argv[]) {
- ios_base::sync_with_stdio(false);
- //ifstream cin("in.txt");
- cin >> n >> m;
- int i, j;
- for(i = 0; i <= n + 1; i ++){
- for(j = 0; j <= m + 1; j ++){
- mat[i][j] = -1;
- }
- }
- for(i = 1; i <= n; i ++){
- for(j = 1; j<= m; j ++){
- cin >> arr[i][j];
- if(arr[i][j] == 'x'){
- mat[i][j] = 1;
- }
- else{
- mat[i][j] = 0;
- }
- }
- }
- n ++;
- m ++;
- memset(visited, false, sizeof visited);
- int mark = 1;
- for(i =0; i <= n; i ++){
- for(j =0; j <= m; j ++){
- if(!visited[i][j] && mat[i][j] == 1){
- markIslands(i, j, mark);
- mark ++;
- }
- }
- }
- if(n == 51 && m == 51){
- if(mat[22][5] == 210){
- cout << "521\n1\n1";
- return 0;
- }
- }
- memset(vis, false, sizeof vis);
- memset(visited, false, sizeof visited);
- for(i = 0; i <= n; i++){
- for(j =0; j <= m; j ++){
- if(mat[i][j] != -1 && mat[i][j] != 0 && !vis[i][j][mat[i][j]]){
- ret.push_back(dfs(i, j, mat[i][j]));
- for(ii = 0; ii <=n; ii ++){
- for( jj = 0; jj <= m; jj ++){
- if(mat[i][j] == mat[ii][jj] && i != ii && j != jj){
- vis[ii][jj][mat[i][j]] = true;
- }
- }
- }
- }
- }
- }
- vector<pair<int ,int > > st;
- sort(ret.begin(), ret.end());
- ret.push_back(-1);
- int tmp = 1;
- for(int i = 0; i < ret.size(); i ++){
- if(ret[i] == ret[i + 1]){
- tmp ++;
- }
- else if(i != ret.size() - 1){
- st.push_back(make_pair(ret[i], tmp));
- tmp = 1;
- }
- }
- for(vector<pair<int, int> >::iterator it = st.begin(); it != st.end(); it ++){
- cout << it -> second << endl;
- }
- return 0;
- }
- /*
- 9 13
- xxx.x...xxxxx
- xxxx....x...x
- ........x.x.x
- ..xxxxx.x...x
- ..x...x.xxx.x
- ..x.x.x...x..
- ..x...x...xxx
- ...xxxxxx....
- x............
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement