#include <iostream>
#include <vector>
using namespace std;
class Rooms
{
public:
// variables
int xs, ys; // map resolution
int **map; // map[xs][ys]
enum
{
_W = 8,
_N = 4,
_E = 2,
_S = 1
};
// internals
Rooms() { map = NULL; xs = 0; ys = 0; }
~Rooms() { _free(); }
// release map memory
void _free()
{
if (map)
{
for (int x = 0; x<xs; x++)
if (map[x])
delete[] map[x];
delete[] map;
}
map = NULL; xs = 0; ys = 0;
}
// inteface
// realloc map to new resolution
void resize(int _xs, int _ys)
{
if ((xs == _xs) && (ys == _ys)) return;
_free();
xs = _xs; ys = _ys;
map = new int*[xs];
for (int x = 0; x<xs; x++)
map[x] = new int[ys];
}
// count rooms
int count()
{
int x, y, i, i0, i1, w0, w1, n, e;
// each block is a separate room
for (n = 0, x = 0; x<xs; x++)
for (y = 0; y<ys; y++, n += 16)
{
map[x][y] &= 0x0000000F; // low 4 bits are walls
map[x][y] |= n & 0xFFFFFFF0; // rest is room index
} n >>= 4;
// reindex all indexes i0 to i1
#define map_reindex(i0,i1) \
for (x=0;x<xs;x++) \
for (y=0;y<ys;y++) \
if (int(map[x][y]&0xFFFFFFF0)==i0) \
{ \
map[x][y]&= 0x0000000F; \
map[x][y]|=i1&0xFFFFFFF0; \
}
// loop until no change has occured
for (e = 1; e;)
{
e = 0;
// merge columns
for (x = 0; x<xs; x++)
for (y = 1; y<ys; y++)
{
w0 = map[x][y - 1] & 0x0000000F;
i0 = map[x][y - 1] & 0xFFFFFFF0;
w1 = map[x][y] & 0x0000000F;
i1 = map[x][y] & 0xFFFFFFF0;
if ((i0 != i1) && (int(w0&_S) == 0) && (int(w1&_N) == 0)) { map_reindex(i0, i1); n--; e = 1; }
}
// merge rows
for (y = 0; y<ys; y++)
for (x = 1; x<xs; x++)
{
w0 = map[x - 1][y] & 0x0000000F;
i0 = map[x - 1][y] & 0xFFFFFFF0;
w1 = map[x][y] & 0x0000000F;
i1 = map[x][y] & 0xFFFFFFF0;
if ((i0 != i1) && (int(w0&_E) == 0) && (int(w1&_W) == 0)) { map_reindex(i0, i1); n--; e = 1; }
}
}
return n;
#undef map_reindex
}
};
int main() {
const vector<char> rooms = { 0b1101, 0b0110, 0b1101, 0b0110, 0b1100, 0b0101, 0b0110,
0b1110, 0b1001, 0b0110, 0b1011, 0b1010, 0b1111, 0b1010,
0b1000, 0b0101, 0b0011, 0b1110, 0b1011, 0b1110, 0b1010,
0b1011, 0b1101, 0b0101, 0b0001, 0b0101, 0b0011, 0b1011 };
const size_t width = 7U;
Rooms test;
test.resize(width, rooms.size() / width);
for (auto y = 0; y < test.ys; ++y) {
for (auto x = 0; x < test.xs; ++x) {
test.map[x][y] = rooms[x + y * width];
}
}
cout << test.count() << endl;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgUm9vbXMKewpwdWJsaWM6CgkvLyB2YXJpYWJsZXMKCWludCB4cywgeXM7ICAgICAgICAgIC8vIG1hcCByZXNvbHV0aW9uCglpbnQgKiptYXA7ICAgICAgICAvLyBtYXBbeHNdW3lzXQoKCWVudW0KCXsKCQlfVyA9IDgsCgkJX04gPSA0LAoJCV9FID0gMiwKCQlfUyA9IDEKCX07CgoJLy8gaW50ZXJuYWxzCglSb29tcygpIHsgbWFwID0gTlVMTDsgeHMgPSAwOyB5cyA9IDA7IH0KCX5Sb29tcygpIHsgX2ZyZWUoKTsgfQoJLy8gcmVsZWFzZSBtYXAgbWVtb3J5Cgl2b2lkIF9mcmVlKCkKCXsKCQlpZiAobWFwKQoJCXsKCQkJZm9yIChpbnQgeCA9IDA7IHg8eHM7IHgrKykKCQkJCWlmIChtYXBbeF0pCgkJCQkJZGVsZXRlW10gbWFwW3hdOwoJCQlkZWxldGVbXSBtYXA7CgkJfQoJCW1hcCA9IE5VTEw7IHhzID0gMDsgeXMgPSAwOwoJfQoKCgkvLyBpbnRlZmFjZQoJLy8gcmVhbGxvYyBtYXAgdG8gbmV3IHJlc29sdXRpb24KCXZvaWQgcmVzaXplKGludCBfeHMsIGludCBfeXMpCgl7CgkJaWYgKCh4cyA9PSBfeHMpICYmICh5cyA9PSBfeXMpKSByZXR1cm47CgkJX2ZyZWUoKTsKCQl4cyA9IF94czsgeXMgPSBfeXM7CgkJbWFwID0gbmV3IGludCpbeHNdOwoJCWZvciAoaW50IHggPSAwOyB4PHhzOyB4KyspCgkJCW1hcFt4XSA9IG5ldyBpbnRbeXNdOwoJfQoKCS8vIGNvdW50IHJvb21zCglpbnQgY291bnQoKQoJewoJCWludCB4LCB5LCBpLCBpMCwgaTEsIHcwLCB3MSwgbiwgZTsKCQkvLyBlYWNoIGJsb2NrIGlzIGEgc2VwYXJhdGUgcm9vbQoJCWZvciAobiA9IDAsIHggPSAwOyB4PHhzOyB4KyspCgkJCWZvciAoeSA9IDA7IHk8eXM7IHkrKywgbiArPSAxNikKCQkJewoJCQkJbWFwW3hdW3ldICY9IDB4MDAwMDAwMEY7ICAgIC8vIGxvdyA0IGJpdHMgYXJlIHdhbGxzCgkJCQltYXBbeF1beV0gfD0gbiAmIDB4RkZGRkZGRjA7ICAgIC8vIHJlc3QgaXMgcm9vbSBpbmRleAoJCQl9IG4gPj49IDQ7CgkJLy8gcmVpbmRleCBhbGwgaW5kZXhlcyBpMCB0byBpMQojZGVmaW5lIG1hcF9yZWluZGV4KGkwLGkxKSAgICAgICAgICAgICAgICAgICAgICBcCiAgICAgICAgZm9yICh4PTA7eDx4czt4KyspICAgICAgICAgICAgICAgICAgICAgICAgICBcCiAgICAgICAgIGZvciAoeT0wO3k8eXM7eSsrKSAgICAgICAgICAgICAgICAgICAgICAgICBcCiAgICAgICAgICBpZiAoaW50KG1hcFt4XVt5XSYweEZGRkZGRkYwKT09aTApICAgICAgXAogICAgICAgICAgICB7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXAogICAgICAgICAgICBtYXBbeF1beV0mPSAgIDB4MDAwMDAwMEY7ICAgICAgICAgICAgICAgXAogICAgICAgICAgICBtYXBbeF1beV18PWkxJjB4RkZGRkZGRjA7ICAgICAgICAgICAgICAgXAogICAgICAgICAgICB9CgkJLy8gbG9vcCB1bnRpbCBubyBjaGFuZ2UgaGFzIG9jY3VyZWQKCQlmb3IgKGUgPSAxOyBlOykKCQl7CgkJCWUgPSAwOwoJCQkvLyBtZXJnZSBjb2x1bW5zCgkJCWZvciAoeCA9IDA7IHg8eHM7IHgrKykKCQkJCWZvciAoeSA9IDE7IHk8eXM7IHkrKykKCQkJCXsKCQkJCQl3MCA9IG1hcFt4XVt5IC0gMV0gJiAweDAwMDAwMDBGOwoJCQkJCWkwID0gbWFwW3hdW3kgLSAxXSAmIDB4RkZGRkZGRjA7CgkJCQkJdzEgPSBtYXBbeF1beV0gJiAweDAwMDAwMDBGOwoJCQkJCWkxID0gbWFwW3hdW3ldICYgMHhGRkZGRkZGMDsKCQkJCQlpZiAoKGkwICE9IGkxKSAmJiAoaW50KHcwJl9TKSA9PSAwKSAmJiAoaW50KHcxJl9OKSA9PSAwKSkgeyBtYXBfcmVpbmRleChpMCwgaTEpOyBuLS07IGUgPSAxOyB9CgkJCQl9CgkJCS8vIG1lcmdlIHJvd3MKCQkJZm9yICh5ID0gMDsgeTx5czsgeSsrKQoJCQkJZm9yICh4ID0gMTsgeDx4czsgeCsrKQoJCQkJewoJCQkJCXcwID0gbWFwW3ggLSAxXVt5XSAmIDB4MDAwMDAwMEY7CgkJCQkJaTAgPSBtYXBbeCAtIDFdW3ldICYgMHhGRkZGRkZGMDsKCQkJCQl3MSA9IG1hcFt4XVt5XSAmIDB4MDAwMDAwMEY7CgkJCQkJaTEgPSBtYXBbeF1beV0gJiAweEZGRkZGRkYwOwoJCQkJCWlmICgoaTAgIT0gaTEpICYmIChpbnQodzAmX0UpID09IDApICYmIChpbnQodzEmX1cpID09IDApKSB7IG1hcF9yZWluZGV4KGkwLCBpMSk7IG4tLTsgZSA9IDE7IH0KCQkJCX0KCQl9CgoJCXJldHVybiBuOwojdW5kZWYgbWFwX3JlaW5kZXgKCX0KfTsKCmludCBtYWluKCkgewoJY29uc3QgdmVjdG9yPGNoYXI+IHJvb21zID0geyAwYjExMDEsCTBiMDExMCwJMGIxMTAxLAkwYjAxMTAsCTBiMTEwMCwJMGIwMTAxLAkwYjAxMTAsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDBiMTExMCwJMGIxMDAxLAkwYjAxMTAsCTBiMTAxMSwJMGIxMDEwLAkwYjExMTEsCTBiMTAxMCwKCSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMGIxMDAwLAkwYjAxMDEsCTBiMDAxMSwJMGIxMTEwLAkwYjEwMTEsCTBiMTExMCwJMGIxMDEwLAoJICAgICAgICAgICAgICAgICAgICAgICAgICAgICAwYjEwMTEsCTBiMTEwMSwJMGIwMTAxLAkwYjAwMDEsCTBiMDEwMSwJMGIwMDExLAkwYjEwMTEgfTsKICAgIGNvbnN0IHNpemVfdCB3aWR0aCA9IDdVOwoJUm9vbXMgdGVzdDsKCgl0ZXN0LnJlc2l6ZSh3aWR0aCwgcm9vbXMuc2l6ZSgpIC8gd2lkdGgpOwoJZm9yIChhdXRvIHkgPSAwOyB5IDwgdGVzdC55czsgKyt5KSB7CgkJZm9yIChhdXRvIHggPSAwOyB4IDwgdGVzdC54czsgKyt4KSB7CgkJCXRlc3QubWFwW3hdW3ldID0gcm9vbXNbeCArIHkgKiB3aWR0aF07CgkJfQoJfQoKCWNvdXQgPDwgdGVzdC5jb3VudCgpIDw8IGVuZGw7ICAgIAp9