fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. #include <set>
  6.  
  7. void connect_check(int n, int complex, int x, int y, std::vector<std::vector<int>> &map) {
  8.  
  9.   if (map[y][x] == 1) {
  10.  
  11.     map[y][x] = complex;
  12.  
  13.     if (x + 1 < n) { // 오른쪽
  14.       if (map[y][x + 1] == 1) {
  15.         connect_check(n, complex, x + 1, y, map);
  16.       }
  17.       else if (map[y][x + 1] > 1) {
  18.         map[y][x] = map[y][x + 1];
  19.       }
  20.     }
  21.     if (y + 1 < n) { // 아래쪽
  22.       if (map[y + 1][x] == 1) {
  23.         connect_check(n, complex, x, y + 1, map);
  24.       }
  25.       else if (map[y + 1][x] > 1) {
  26.         map[y][x] = map[y + 1][x];
  27.       }
  28.     }
  29.     if (x > 0) { // 왼쪽
  30.       if (map[y][x - 1] == 1) {
  31.         connect_check(n, complex, x - 1, y, map);
  32.       }
  33.       else if (map[y][x - 1] > 1) {
  34.         map[y][x] = map[y][x - 1];
  35.       }
  36.     }
  37.     if (y > 0) { // 위쪽
  38.       if (map[y - 1][x] == 1) {
  39.         connect_check(n, complex, x, y - 1, map);
  40.       }
  41.       else if (map[y - 1][x] > 1) {
  42.         map[y][x] = map[y - 1][x];
  43.       }
  44.     }
  45.  
  46.   }
  47.  
  48.   for (int i = 0; i < n; i++) {
  49.     for (int j = 0; j < n; j++) {
  50.       if (map[i][j] == 1) {
  51.         connect_check(n, complex + 1, j, i, map);
  52.       }
  53.     }
  54.   }
  55.  
  56.   return;
  57. }
  58.  
  59. int main(void) {
  60.  
  61.   std::string line;
  62.   int n;
  63.   int complex = 0;
  64.  
  65.   std::cin >> n;
  66.  
  67.   std::vector<std::vector<int>> map(n, std::vector<int>(n));
  68.   std::vector<int> complexes(n*n);
  69.   std::set<int> count_complex;
  70.  
  71.   for (int i = 0; i < n; i++) {
  72.     std::cin >> line;
  73.     for (int j = 0; j < n; j++) {
  74.       map[i][j] = line[j] - '0'; // char '1' 을 int 1로 변환
  75.     }
  76.   }
  77.  
  78.   connect_check(n, 2, 0, 0, map);
  79.  
  80.   for (int i = 0; i < n; i++) {
  81.     for (int j = 0; j < n; j++) {
  82.       if (map[i][j] > 0) {
  83.         complexes[map[i][j]]++;
  84.         count_complex.insert(map[i][j]);
  85.       }
  86.     }
  87.   }
  88.  
  89.   std::sort(complexes.begin(), complexes.end());
  90.  
  91.   std::cout << count_complex.size() << std::endl;
  92.  
  93.   for (std::vector<int>::iterator itr = complexes.begin(); itr != complexes.end(); ++itr) {
  94.     if (*itr != 0) {
  95.       std::cout << *itr << std::endl;
  96.     }
  97.   }
  98.  
  99.   return 0;
  100. }
Success #stdin #stdout 0s 4328KB
comments (?)
stdin
copy 
5
11000
10000
10000
10000
00000
stdout
copy 
2
2
3
https://ideone.com/eqVIIX
language:
C++14 (gcc 8.3)
created:
4 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!