Побудова

• перший рядок повністю заповнюємо символами R;

• останній рядок повністю заповнюємо символами B;

• кожен проміжний рядок робимо однаковим: RBRB....

У кожному стовпці є червона клітинка в першому рядку та синя в останньому. Усі червоні клітинки проміжних рядків вертикально доходять до першого рядка, тому червона область зв’язна. Аналогічно всі сині клітинки доходять до останнього рядка.

У будь-яких двох сусідніх стовпцях проміжний рядок містить обидва кольори. Тому кожен квадрат $2\times 2$ між проміжними рядками містить обидва кольори. Те саме виконується на межах із першим та останнім рядками. Для $n=2$ маємо один червоний і один синій рядок, що також є правильною побудовою.

Складність

Потрібно вивести n^2 символів: час O(n^2), додаткова пам’ять $O(n)$.