| Codeforces Round 192 (Div. 1) |
|---|
| Закончено |
Вы — искатель приключений. Сейчас Вы путешествуете по злому храму. Одолев пару злых зомби, Вы прибыли в квадратную комнату, состоящую из плиток, выложенных в таблицу размера n × n. Строки пронумерованы от 1 до n сверху вниз, а столбцы пронумерованы с 1 до n слева направо. В дальнем углу комнаты находится дверь, закрытая злыми магическими силами. На двери написано следующее:
Так как Вы довольно опытный искатель приключений, Вы мгновенно понимаете, в чем тут дело. Вы замечаете, что каждая ячейка в таблице изначально является злой. Надо очистить все эти ячейки.
Единственный известный Вам способ очищения плиток — заклинание «Очищение». Заклинание накладывается на одну плитку, а затем все ячейки в той же строке, а также все ячейки в том же столбце (включая выбранную плитку) очищаются! Разрешается очищать клетку несколько раз.
Вы хотели бы очистить все n × n ячеек, накладывая заклинание очищения как можно меньше раз. В теории все просто, но вы только что заметили, что есть еще особо злые плитки. На них заклинание очищения нельзя накладывать, даже после того, как они были очищены. Но эти плитки все же можно очистить, если наложить заклинание очищения на ячейку в той же строке или столбце.
Пожалуйста, найдите способ очистить все ячейки минимальным количеством накладываемых заклинаний. Если такого способа нет, выведите -1.
В первой строке записано единственное целое число n (1 ≤ n ≤ 100). В следующих n строках записано по n символов: j-ый символ i-ой строки обозначает ячейку, расположенную в строке i и столбце j. Особо злые плитки заданы символом «E», остальные — символом «.».
Если очистить все клетки не удастся, то выведите -1. В противном случае, если Ваше решение накладывает x заклинаний очищения, выведите x строк. Каждая строка должна состоять из двух целых чисел, обозначающих номер строки и столбца ячейки, на которую следует наложить заклинание очищения.
3
.E.
E.E
.E.
1 1
2 2
3 3
3
EEE
E..
E.E
-1
5
EE.EE
E.EE.
E...E
.EE.E
EE.EE
3 3
1 3
2 2
4 4
5 3
Первый пример иллюстрируется следующим образом. Фиолетовым выделены неочищенные злые плитки. Красным выделена плитка, на которую наложено заклинание очищения. Желтым выделены плитки, на которые распространяется текущее заклинание (возможно, ранее они уже были очищены). Зеленым выделены ранее очищенные плитки.
Во втором примере очистить ячейку, расположенную в строке 1 и столбце 1, невозможно.
К третьему примеру:
