fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <utility>
  5. #include <stack>
  6.  
  7. using namespace std;
  8.  
  9. void print_vector_2d(const std::vector<std::vector<int>>& vec) {
  10.     std::cout << "[\n";
  11.     for (size_t i = 0; i < vec.size(); ++i) {
  12.         std::cout << "[";
  13.         for (size_t j = 0; j < vec[i].size(); ++j) {
  14.             std::cout << vec[i][j];
  15.             if (j < vec[i].size() - 1) {
  16.                 std::cout << ", ";
  17.             }
  18.         }
  19.         std::cout << "]";
  20.         if (i < vec.size() - 1) {
  21.             std::cout << ",\n";
  22.         }
  23.     }
  24.     std::cout << "\n]" << std::endl;
  25. }
  26.  
  27. int main() {
  28.     int n, m;
  29.     cin >> n >> m;
  30.  
  31.     vector<string> boxes(n);
  32.     for (int i = 0; i < n; i++) cin >> boxes[i];
  33.  
  34.     vector<pair<int, int>> v;
  35.     for (int i = 0; i < n; i++) {
  36.         for (int j = 0; j < m; j++) {
  37.             if (boxes[i].substr(j, 1) == "#") v.push_back(make_pair(i, j));
  38.         }
  39.     }
  40.  
  41.     vector<vector<int>> component(n, vector<int>(m, -1));
  42.     int num = 0;
  43.     stack<pair<int, int>> s;
  44.     pair<int, int> now, i;
  45.  
  46.     for (pair<int, int> u : v) {
  47.         if (component[u.first][u.second] != -1) continue;
  48.  
  49.         s = stack<pair<int, int>>(); s.push(u);
  50.         component[u.first][u.second] = num;
  51.  
  52.         while (!s.empty()) {
  53.             now = s.top();
  54.             s.pop();
  55.  
  56.             i = make_pair(now.first+1, now.second);
  57.             if (
  58.                 i.first >= 0 && i.first < n
  59.                 && i.second >= 0 && i.second < m
  60.                 && boxes[i.first].substr(i.second, 1) == "#"
  61.                 && component[i.first][i.second] == -1
  62.             ) {
  63.                 s.push(i);
  64.                 component[i.first][i.second] = num;
  65.             }
  66.  
  67.             i = make_pair(now.first-1, now.second);
  68.             if (
  69.                 i.first >= 0 && i.first < n
  70.                 && i.second >= 0 && i.second < m
  71.                 && boxes[i.first].substr(i.second, 1) == "#"
  72.                 && component[i.first][i.second] == -1
  73.             ) {
  74.                 s.push(i);
  75.                 component[i.first][i.second] = num;
  76.             }
  77.  
  78.             i = make_pair(now.first, now.second+1);
  79.             if (
  80.                 i.first >= 0 && i.first < n
  81.                 && i.second >= 0 && i.second < m
  82.                 && boxes[i.first].substr(i.second, 1) == "#"
  83.                 && component[i.first][i.second] == -1
  84.             ) {
  85.                 s.push(i);
  86.                 component[i.first][i.second] = num;
  87.             }
  88.  
  89.             i = make_pair(now.first, now.second-1);
  90.             if (
  91.                 i.first >= 0 && i.first < n
  92.                 && i.second >= 0 && i.second < m
  93.                 && boxes[i.first].substr(i.second, 1) == "#"
  94.                 && component[i.first][i.second] == -1
  95.             ) {
  96.                 s.push(i);
  97.                 component[i.first][i.second] = num;
  98.             }
  99.  
  100.             cout << num << " ";
  101.             num++;
  102.             print_vector_2d(component);
  103.         }
  104.     }
  105.  
  106.     cout << num << "\n";
  107.  
  108.     vector<int> cc_sizes(num);
  109.     for (int i = 0; i < n; i++) {
  110.         for (int j = 0; j < m; j++) {
  111.             if (component[i][j] != -1) cc_sizes[component[i][j]]++;
  112.         }
  113.     }
  114.  
  115.     int max = 0;
  116.     for (int i = 0; i < num; i++) {
  117.         if (cc_sizes[i] > max) max = cc_sizes[i];
  118.     }
  119.  
  120.     cout << max << "\n";
  121. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
5 6
..##..
..##..
.#....
###..#
.#..#.
stdout
copy 
0 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, -1, -1, -1],
[-1, -1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1, -1]
]
1 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, -1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1, -1]
]
2 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, -1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1, -1]
]
3 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, -1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1, -1]
]
4 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, 4, -1, -1, -1, -1],
[-1, 4, -1, -1, -1, -1],
[-1, -1, -1, -1, -1, -1]
]
5 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, 4, -1, -1, -1, -1],
[5, 4, 5, -1, -1, -1],
[-1, 5, -1, -1, -1, -1]
]
6 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, 4, -1, -1, -1, -1],
[5, 4, 5, -1, -1, -1],
[-1, 5, -1, -1, -1, -1]
]
7 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, 4, -1, -1, -1, -1],
[5, 4, 5, -1, -1, -1],
[-1, 5, -1, -1, -1, -1]
]
8 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, 4, -1, -1, -1, -1],
[5, 4, 5, -1, -1, -1],
[-1, 5, -1, -1, -1, -1]
]
9 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, 4, -1, -1, -1, -1],
[5, 4, 5, -1, -1, 9],
[-1, 5, -1, -1, -1, -1]
]
10 [
[-1, -1, 0, 0, -1, -1],
[-1, -1, 0, 1, -1, -1],
[-1, 4, -1, -1, -1, -1],
[5, 4, 5, -1, -1, 9],
[-1, 5, -1, -1, 10, -1]
]
11
3
https://ideone.com/k1Ovur
language:
C++14 (gcc 8.3)
created:
3 hours 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!