この問題の調査：https://twitter.com/mathmathsan/status/1234116541366427648

infection.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

#define rep(i,n)	for(lint i = 0; i < n; i++)
#define repr(i,n)	for(lint i = n - 1; i >= 0; i--)
#define repb(i,start,end)	for(lint i = start; i <= end; i++)
#define repbr(i,start,end)	for(lint i = end; i >= start; i--)

#define all(v) v.begin(),v.end()

using lint = long long;
using vec = vector<lint>;
class vec2 : public vector<vector<lint>>
{
public:
	vec2(lint h, lint w) : vector(h, vector<lint>(w)) {}
	vec2(lint h, lint w, lint v) : vector(h, vector<lint>(w, v)) {}
};

template<class It, class It2>
auto spacel(It i, It2 end)
{
	if (i + 1 == end)
	{
		return '\n';
	}
	else
	{
		return ' ';
	}
}

template<class It>
bool next_comb(lint n, It begin, It end)
{
	auto rend = make_reverse_iterator(begin);
	auto rbegin = make_reverse_iterator(end);

	auto rit = rbegin;
	for (; rit != rend; rit++)
	{
		if ((rit == rbegin && (*rit) + 1 != n) ||
			(rit != rbegin && (*rit) + 1 != *(rit - 1)))
		{
			goto found;
		}
	}
	return false;
found:;
	(*rit)++;

	for (auto it = rit.base(); it != end; it++)
	{
		(*it) = (*(it - 1)) + 1;
	}
	return true;
}

lint f(vec& init)
{
	vec2 m(8, 8, 0);

	rep(i, init.size())
	{
		lint x = init[i] % 6 + 1;
		lint y = init[i] / 6 + 1;

		m[x][y] = 1;
	}

	lint gen = 1;
	while (1)
	{
		gen++;
		lint upd = 0;

		repb(x, 1, 6)
		{
			repb(y, 1, 6)
			{
				if (m[x][y] == 1)
					continue;
				lint k = 0;
				k += m[x - 1][y] == 1;
				k += m[x + 1][y] == 1;
				k += m[x][y - 1] == 1;
				k += m[x][y + 1] == 1;

				if (k >= 2)
					m[x][y] = 2;
			}
		}

		lint rem = 0;
		repb(x, 1, 6)
		{
			repb(y, 1, 6)
			{
				if (m[x][y] == 2)
				{
					m[x][y] = 1; upd++;
				}
				if (m[x][y] == 0)
					rem++;
			}
		}

		if (upd == 0 && rem > 0)
		{
			return -1;
		}
		if (rem == 0)
		{
			return gen;
		}
	}
}

int main()
{
	lint max_record = 0;

	repb(n, 1, 36 - max_record)
	{
		cout << "infection: " << n << endl;
		vec h(n);

		lint record = 0;

		iota(all(h), 0);

		do
		{
			lint tmp = f(h);
			if (tmp > record)
			{
				record = tmp;
				cout << "New Record: " << setw(3) << record << " : ";
				rep(i, n)
				{
					cout << "(" << h[i] % 6 + 1 << "," << h[i] / 6 + 1 << ")" << spacel(i, n);
				}
			}
		} while (next_comb(36, all(h)));

		cout << endl;
	}

	return 0;
}