#include <bitset> #include <iostream> #include <vector> using namespace std; #define ITER 14 #define MAX (2LL<<ITER) bitset<MAX*MAX> *grid = 0; int encode(int x, int y) { return x*MAX + y; } void decode(int c, int &x, int &y) { x = c/MAX; y = c%MAX; } bool get(int x, int y) { if (x<0 || y<0) { return false; } else if (x>=MAX || y>=MAX) { // the end exit(0); } else { return grid->test(encode(x,y)); } } bool atCorner(int x, int y) { if ((get(x-1,y) || get(x+1,y)) && (get(x,y-1) || get(x,y+1))) { return true; } else { return false; } } void set(int x, int y) { grid->set(encode(x,y)); } void reset(int x, int y) { grid->reset(encode(x,y)); } vector<int> gen; vector<int> newgen; void explore(int x, int y, int dx, int dy) { while (get(x+=dx, y+=dy) && get(x+=dx, y+=dy)) { reset(x,y); if (atCorner(x,y)) { newgen.push_back(encode(x,y)); return; } } } void explore(int c) { int x, y; decode(c, x, y); explore(x, y, +1, 0); explore(x, y, -1, 0); explore(x, y, 0, +1); explore(x, y, 0, -1); } int main() { grid = new bitset<MAX*MAX>; for (int b=0; b<MAX; b++) { set(b,0); set(0,b); } int s = MAX; // step size int r = 1; // # of rectangles for (int n=1; n<=ITER; n++) { // cut vertically for (int x = s/2; x<MAX; x+=s) { bool prec = false; bool write = false; for (int y = 0; y<MAX; y++) { bool curr = get(x,y); if (prec && !curr) { write = !write; if (write) { r++; } } if (write) { set(x,y); } prec = curr; } } // cut horizontally for (int y = s/2; y<MAX; y+=s) { bool prec = false; bool write = false; for (int x = 0; x<MAX; x++) { bool curr = get(x,y); if (prec && !curr) { write = !write; if (write) { r++; } } if (write) { set(x,y); } prec = curr; } } s/=2; } gen.push_back(encode(0,0)); reset(0,0); cout << 0 << ' ' << gen.size() << endl; for (int n=1;; n++) { for (size_t k=0; k<gen.size(); k++) { explore(gen[k]); } gen = newgen; newgen.clear(); cout << n << ' ' << gen.size() << endl; } return 0; }