fork download
copy 
  1. #include <iostream> // using g++ -Wall -std=c++14
  2. #include <vector>
  3. #include <set>
  4. #include <bitset>
  5. #include <numeric>
  6. using namespace std;
  7.  
  8. int m, n, ans; // room of m x n dimensions
  9. vector<string> floorPlan; // each string is 4 char long composed of '0' and '1'
  10. vector<int> parent, ranks; // each room is a seperate component in worst case
  11.  
  12. int findSet(int x) {
  13.   if(parent[x] != x)
  14.     parent[x] = findSet(parent[x]);
  15.   return parent[x];
  16. }
  17.  
  18. void unionSet(int x, int y) {
  19.   int px = findSet(x);
  20.   int py = findSet(y);
  21.  
  22.   if(ranks[px] > ranks[py])
  23.     parent[py] = px;
  24.   else
  25.     parent[px] = py;
  26.  
  27.   if(ranks[px] == ranks[py])
  28.     ranks[py]++;
  29. }
  30.  
  31. void inp() {
  32.   string temp;
  33.  
  34.   cin >> m >> n;
  35.  
  36.   for(int i=0; i<m; i++)
  37.     for(int j=0; j<n; j++) {
  38.       cin >> temp;
  39.       floorPlan.push_back(temp);
  40.     }
  41. }
  42.  
  43. void solve() {
  44.   // set up Disjoint Sets
  45.   parent.resize(m*n);
  46.   ranks.resize(m*n, 0);
  47.   iota(parent.begin(), parent.end(), 0);
  48.  
  49.   for(int i=0; i<m; i++)
  50.     for(int j=0; j<n; j++) {
  51.       bitset<4> tile(floorPlan[i*n+j]);
  52.  
  53.       // process West wall
  54.       if(j > 0 && (tile[3] == 0))
  55.         unionSet(i*n+j, i*n+j-1);
  56.  
  57.       // process North wall
  58.       if(i > 0 && (tile[2] == 0))
  59.         unionSet(i*n+j, (i-1)*n+j);
  60.     }
  61.  
  62.   set<int> temp;
  63.   for(int i=0; i<m*n; i++) {
  64.     // normalise each tile
  65.     parent[i] = findSet(parent[i]);
  66.     temp.insert(parent[i]);
  67.   }
  68.  
  69.   ans = temp.size();
  70. }
  71.  
  72. void outp() {
  73.   for(int i=0; i<m; i++) {
  74.     for(int j=0; j<n; j++)
  75.       cout << parent[i*n+j] << "  ";
  76.     cout << endl;
  77.   }
  78.  
  79.   cout << "\n" << ans << endl;
  80. }
  81.  
  82. int main() {
  83.   inp();
  84.   solve();
  85.   outp();
  86.   return 0;
  87. }
  88.  
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
4 7
1101 0110 1101 0110 1100 0101 0110 
1110 1001 0110 1011 1010 1111 1010 
1000 0101 0011 1110 1011 1110 1010 
1011 1101 0101 0001 0101 0011 1011
stdout
copy 
0  0  2  2  4  4  4  
0  0  0  2  4  12  4  
0  0  0  22  4  22  4  
0  22  22  22  22  22  4  

5
https://ideone.com/54YAuM
Quirk's answer to http://stackoverflow.com/q/37867723/2844164
language:
C++14 (gcc 8.3)
created:
9 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!