1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
// PA2025, @mjm, r5c-mig

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
using namespace std;
using ull = unsigned long long;
inline int nextInt() { int n; scanf("%d", &n); return n; }
inline ull nextUll() { ull n; scanf("%llu", &n); return n; }
inline int myMin(int a, int b) { return a <= b ? a : b; }
inline ull myMax(ull a, ull b) { return a >= b ? a : b; }

using State = vector<vector<int>>;

void tick(State& s) {
	int h = s.size();
	int w = s[0].size();
	set<pair<int, int>> toChange;
	for (int r = 1; r < h; ++r) for (int c = 1; c < w; ++c) {
		if (s[r - 1][c - 1] != s[r][c]) continue;
		if (s[r - 1][c] != s[r][c - 1]) continue;
		if (s[r - 1][c] == s[r][c]) continue;
		toChange.insert({ r - 1, c - 1 });
		toChange.insert({ r - 1, c });
		toChange.insert({ r, c - 1 });
		toChange.insert({ r, c });
	}
	for (auto it = toChange.begin(); it != toChange.end(); ++it) {
		int r = it->first;
		int c = it->second;
		s[r][c] = 1 - s[r][c];
	}
}

int run(State s) {
	set<State> visited;
	while (true) {
		//fprintf(stderr, "size: %d\n", visited.size());
		if (visited.count(s) > 0)
			return visited.size();
		visited.insert(s);
		tick(s);
	}
	// unreachable
	return -1;
}

int main() {

	// test
	{
		State s;
		for (int r = 0; r < 100; ++r) {
			if (0 == r % 2) {
				s.push_back(vector<int>(100, 1));
			} else {
				s.push_back(vector<int>(100, 0));
			}
			s[r][0] = 0;
			s[r][99] = 1;
		}
		s[99][0] = 1;
		s[99][99] = 0;

		//int res = run(s);
		//printf("%d\n", res);

		for (int r = 0; r < 100; ++r) {
			for (int c = 0; c < 100; ++c) {
				printf("%d", s[r][c]);
			}
			printf("\n");
		}

		return 0;
	}

	const int h = 4;
	const int w = 4;
	const int MASK_END = 1 << (h * w);

	int best = 0;

	for (int mask = 0; mask < MASK_END; ++mask) {
		State s(h, vector<int>(w));
		int tmp = mask;
		for (int r = 0; r < h; ++r) for (int c = 0; c < w; ++c) {
			s[r][c] = tmp & 1;
			tmp >>= 1;
		}

		int cur = run(s);
		if (cur > best) best = cur;
		if (cur == best) {
			printf("Result %d\n", cur);
			for (int r = 0; r < h; ++r) {
				for (int c = 0; c < w; ++c)
					printf("%d", s[r][c]);
				printf("\n");
			}
		}
	}

	return 0;
}