← 返回题目列表

Codeforces · 329/A

A. 净化

中文机器翻译题面 查看原题

你是一名冒险家,目前正在一座邪恶的神庙中旅行。击败几只弱小的僵尸后,你到达了一个由瓷砖组成 n × n 网格的方形房间。行从上到下编号为 1 到 n,列从左到右编号为 1 到 n。房间的另一边有一扇被邪恶魔法力量锁着的门。门上刻有以下铭文:

清洗一切邪恶将唤醒之门!

作为一名非常资深的冒险家,你立即意识到这意味着什么。您注意到网格中的每个单元格最初都是邪恶的。您应该纯化所有这些细胞。

你所知道的唯一净化瓷砖的方法是施展“净化”法术。你在单个图块上施放这个法术——然后,与所选图块位于同一行和同一列的所有单元格都会被净化(包括所选图块)!允许多次纯化细胞。

你想净化所有 n × n 个细胞,同时尽量减少施展“净化”法术的次数。这听起来很简单,但您刚刚注意到有些瓷砖比其他瓷砖特别邪恶。你不能对那些特别邪恶的瓷砖施放“净化”法术,即使它们被净化后也是如此。如果共享同一行或同一列的单元格被“净化”咒语选中,它们仍然可以被净化。

请找到某种方法以最少的施法次数净化所有细胞。如果没有这样的方法,则打印-1。

输入

第一行将包含一个整数 n (1 ≤ n ≤ 100)。然后,接下来有 ​​n 行,每行包含 n 个字符。第 i 行中的第 j 个字符表示位于第 i 行 j 列的单元格。如果它是一个特别更邪恶的单元格,它将是字符“E”,并且“.”。否则。

输出

如果无法纯化所有细胞,则输出-1。否则,如果您的解决方案施放 x 个“净化”法术(其中 x 是可能的最小法术数),则输出 x 行。每行应包含两个整数,表示您应对其施放“净化”咒语的单元格的行号和列号。

示例

输入 #1

3
.E.
E.E
.E.

输出 #1

1 1
2 2
3 3

输入 #2

3
EEE
E..
E.E

输出 #2

-1

输入 #3

5
EE.EE
E.EE.
E...E
.EE.E
EE.EE

输出 #3

3 3
1 3
2 2
4 4
5 3

注意

第一示例说明如下。紫色瓦片是尚未净化的邪恶瓦片。红色瓷砖是施放“净化”的瓷砖。黄色瓷砖是由于当前“净化”法术而被净化的瓷砖。绿色瓷砖是之前经过净化处理的瓷砖。

在第二个示例中,无法纯化位于第 1 行第 1 列的单元格。

对于第三个示例: