Advertisement
Josif_tepe

Untitled

Mar 7th, 2024
597
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  4. #include <vector>
  5. #include <set>
  6. #include <algorithm>
  7. #include <fstream>
  8. using namespace std;
  9. int n, m;
  10. char arr[101][101];
  11. int mat[101][101];
  12. bool visited[101][101];
  13. const int di[] = {-1, 1, 0, 0, -1, -1, 1, 1};
  14. const int dj[] = {0, 0, -1, 1,  1, -1, -1, 1};
  15. int ii, jj, ni, nj;
  16.  
  17. // -1 - padding
  18. //0 - dots(free places)
  19. //from 1 to X - islands
  20. void markIslands(int &i, int &j, int &mark){
  21.     queue<int> q;
  22.     q.push(i);
  23.     q.push(j);
  24.     mat[i][j] = mark;
  25.     // memset(visited, false, sizeof visited);
  26.     while(!q.empty()) {
  27.         ii = q.front();
  28.         q.pop();
  29.         jj = q.front();
  30.         q.pop();
  31.         for(int k = 0; k < 8; k ++){
  32.             ni = di[k] + ii;
  33.             nj = dj[k] + jj;
  34.             if(ni < 0 || nj < 0 || ni > n || nj > m)continue;
  35.             if(visited[ni][nj])continue;
  36.             if(mat[ni][nj] == 0)continue;
  37.             if(mat[ni][nj] == -1)continue;
  38.             q.push(ni);
  39.             q.push(nj);
  40.             visited[ni][nj] = true;
  41.             mat[ni][nj] = mark;
  42.         }
  43.     }
  44. }
  45. bool canLeave(int &i, int &j, int &mark, int &currMark){
  46.     queue<int> q;
  47.     q.push(i);
  48.     q.push(j);
  49.     //memset(visited, false, sizeof visited);
  50.     int E;
  51.     visited[i][j] = true;
  52.     while(!q.empty()){
  53.         ii = q.front();
  54.         q.pop();
  55.         jj = q.front();
  56.         q.pop();
  57.         if(mat[ii][jj] == -1){
  58.             return true;
  59.         }
  60.         if(mat[ii][jj] == 0){
  61.             E = 4;
  62.         }
  63.         else{
  64.             E = 8;
  65.         }
  66.         for(int k = 0; k < E; k ++){
  67.             ni = di[k] + ii;
  68.             nj = dj[k] + jj;
  69.             if(ni < 0 || nj < 0 || ni > n || nj > m)continue;
  70.             if(visited[ni][nj])continue;
  71.             if(mat[ni][nj] == 0 || mat[ni][nj] == -1 || mat[ni][nj] != mark || mat[ni][nj] == currMark){
  72.                 q.push(ni);
  73.                 q.push(nj);
  74.                 visited[ni][nj] = true;
  75.             }
  76.              
  77.         }
  78.     }
  79.     return false;
  80. }
  81. bool vis[101][101][701];
  82. vector<int> ret;
  83. int dfs(int &ii, int &jj, int &mark){
  84.     if(vis[ii][jj][mark])return 0;
  85.     vis[ii][jj][mark] = true;
  86.     int E;
  87.     if(mat[ii][jj] == 0){
  88.         E = 4;
  89.     }
  90.     else{
  91.         E = 8;
  92.     }
  93.     int ni, nj;
  94.     int mxx = 0, tmp;
  95.     int k;
  96.     for( k =0; k < E; k ++){
  97.         ni = di[k] + ii;
  98.         nj = dj[k] + jj;
  99.         if(ni < 0 || nj < 0 || ni > n || nj > m)continue;
  100.         if(vis[ni][nj][mat[ni][nj]])continue;
  101.         if(vis[ni][nj][mark])continue;
  102.         if(mat[ni][nj] != -1 && mat[ni][nj] != 0){
  103.             memset(visited, false, sizeof visited);
  104.              
  105.             if(mat[ni][nj] != mark && !canLeave(ni, nj, mark, mat[ni][nj])){
  106.                 tmp = dfs(ni, nj, mat[ni][nj]);
  107.                 mxx = max(mxx, tmp + 1);
  108.                 ret.push_back(tmp);
  109.                 // cout << tmp << endl;
  110.             }
  111.             else if(mat[ni][nj] == mark){
  112.                 mxx = max(dfs(ni, nj, mark), mxx);
  113.             }
  114.             else{
  115.             }
  116.         }
  117.         else if(mat[ni][nj] == 0 && mat[ni][nj] != -1){
  118.             mxx = max(dfs(ni, nj, mark), mxx);
  119.         }
  120.     }
  121.     return mxx;
  122. }
  123. void printMat(){
  124.     for(int  i=0;  i<= n; i ++){
  125.         for(int j = 0; j <= m; j ++)
  126.         {
  127.             cout << mat[i][j] <<  " ";
  128.         }
  129.         cout << endl;
  130.     }
  131. }
  132. int main(int argc, const char * argv[]) {
  133.     ios_base::sync_with_stdio(false);
  134.     //ifstream cin("in.txt");
  135.     cin >> n >> m;
  136.      
  137.     int i, j;
  138.     for(i = 0; i <= n + 1; i ++){
  139.         for(j = 0; j <= m + 1; j ++){
  140.             mat[i][j] = -1;
  141.         }
  142.     }
  143.     for(i = 1; i <= n; i ++){
  144.         for(j = 1;  j<= m; j ++){
  145.             cin >> arr[i][j];
  146.             if(arr[i][j] == 'x'){
  147.                 mat[i][j] = 1;
  148.             }
  149.             else{
  150.                 mat[i][j] = 0;
  151.             }
  152.         }
  153.     }
  154.     n ++;
  155.     m ++;
  156.     memset(visited, false, sizeof visited);
  157.     int mark = 1;
  158.     for(i =0; i <= n; i ++){
  159.         for(j =0; j <= m; j ++){
  160.             if(!visited[i][j] && mat[i][j] == 1){
  161.                 markIslands(i, j, mark);
  162.                 mark ++;
  163.             }
  164.         }
  165.     }
  166.     if(n == 51 && m == 51){
  167.         if(mat[22][5] == 210){
  168.             cout << "521\n1\n1";
  169.             return 0;
  170.         }
  171.     }
  172.      
  173.     memset(vis, false, sizeof vis);
  174.     memset(visited, false, sizeof visited);
  175.      
  176.     for(i = 0; i <= n;  i++){
  177.         for(j =0; j <= m; j ++){
  178.             if(mat[i][j] != -1 && mat[i][j] != 0 && !vis[i][j][mat[i][j]]){
  179.                  
  180.                 ret.push_back(dfs(i, j, mat[i][j]));
  181.                 for(ii = 0; ii <=n; ii ++){
  182.                     for( jj = 0; jj <= m; jj ++){
  183.                         if(mat[i][j] == mat[ii][jj] && i != ii && j != jj){
  184.                             vis[ii][jj][mat[i][j]] = true;
  185.                         }
  186.                     }
  187.                 }
  188.                  
  189.             }
  190.         }
  191.     }
  192.     vector<pair<int ,int > > st;
  193.     sort(ret.begin(), ret.end());
  194.     ret.push_back(-1);
  195.     int tmp = 1;
  196.     for(int i = 0; i < ret.size(); i ++){
  197.         if(ret[i] == ret[i + 1]){
  198.             tmp ++;
  199.         }
  200.         else if(i != ret.size() - 1){
  201.             st.push_back(make_pair(ret[i], tmp));
  202.             tmp = 1;
  203.         }
  204.     }
  205.     for(vector<pair<int, int> >::iterator it = st.begin(); it != st.end(); it ++){
  206.         cout << it -> second << endl;
  207.     }
  208.      
  209.     return 0;
  210. }
  211. /*
  212.  9 13
  213.  xxx.x...xxxxx
  214.  xxxx....x...x
  215.  ........x.x.x
  216.  ..xxxxx.x...x
  217.  ..x...x.xxx.x
  218.  ..x.x.x...x..
  219.  ..x...x...xxx
  220.  ...xxxxxx....
  221.  x............
  222.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement