Существует множество вариантов игры в крестики и нолики. Рассмотрим одну из них.
На клетчатой квадратной доске расставлено некоторое количество крестиков и ноликов, а также оставлены пустые клетки. Игрок должен заполнить пустые клетки так, чтобы ни крестики ни нолики не образовали линии более чем из трех одинаковых значков подряд. Линии учитываются по горизонтали, вертикали или любой диагонали.
Вашей задачей будет написать программу, которая по заданному начальному полю заполнит все пустые клетки крестиками и ноликами по описанным выше правилам. Если таких расстановок несколько, то правильной будет считаться любая из них.
Гарантируется, что для входных данных, существует хотя бы одно правильное решение.
Первая строка входного файла содержит число $$$n$$$ — размер доски $$$(3 \lt n \le 20)$$$. Далее следуют $$$n$$$ строк по $$$n$$$ символов в каждой — начальное состояние игрового поля. Крестик обозначается знаком «+» (плюс), нолик — символом «0» (нуль), пустое поле — символом «.» (точка).
Формат выходных идентичен формату входных данных (включая размер доски). Решение не должно содержать пустых полей.
4
0.0.
00+0
0+00
++..
4
0+00
00+0
0+00
++0+
