← 返回题目列表

Codeforces · 1421/B

B. 在墙上砌砖

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

平克·弗洛伊德 (Pink Floyd) 正在对罗杰·沃特斯 (Roger Waters) 恶作剧。他们知道他不喜欢墙壁,他希望能够自由行走,所以他们阻止他离开他的房间,这个房间可以看作是一个网格。

Roger Waters 有一个大小为 $$$n\times n$$$ 的方形网格,他想从左上角 ($$$1,1$$$) 到右下角 ($$$n,n$$$) 遍历网格。只要沃特斯仍在网格中,他就可以从一个方格移动到与边相邻的任何其他方格。另外,除了单元格 ($$$1,1$$$) 和 ($$$n,n$$$) 之外,每个单元格中都有一个值 $$$0$$$ 或 $$$1$$$ 。

在开始遍历之前,他将选择 $$$0$$$ 或 $$$1$$$,并且只能转到等于他选择的数字的单元格值。起始和结束单元格 ($$$1,1$$$) 和 ($$$n,n$$$) 不受此规则的约束,无论选择的数字是什么,他都可以遍历它们。因此,单元格 ($$$1,1$$$) 的值为字母“S”,单元格 ($$$n,n$$$) 的值为字母“F”。

例如,在第一个示例测试用例中,他可以通过使用此路径上的零从 ($$$1, 1$$$) 到 ($$$n, n$$$): ($$$1, 1$$$), ($$$2, 1$$$), ($$$2, 2$$$), ($$$2, 3$$$), ($$$3, 3$$$), ($$$3, 4$$$), ($$$4, 4$$$)

乐队的其他成员 (Pink Floyd) 希望 Waters 无法进行遍历,因此当他不看时,他们最多会反转网格中的两个单元格(从 $$$0$$$ 到 $$$1$$$ 或反之亦然)。他们担心自己速度不够快,并请求您帮助选择细胞。 请注意,您不能反转单元格 $$$(1, 1)$$$ 和 $$$(n, n)$$$。

我们可以证明对于给定的约束总是存在一个解决方案。

另请注意,Waters 将在乐队更改其网格后选择他的遍历数字,因此无论他选择哪个数字,他都一定无法到达 ($$$n,n$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 200$$$)。

每个测试用例的以下 $$$n$$$ 行包含二进制网格,正方形($$$1, 1$$$)用“S”着色,正方形($$$n, n$$$)用“F”着色。

$$$n$$$ 的值总和不超过 $$$200$$$。

输出

对于第一行的每个测试用例输出,整数 $$$c$$$ ($$$0 \le c \le 2$$$) — 反转单元格的数量。

在以下 $$$c$$$ 行中的第 $$$i$$$ 行中,打印您反转的第 $$$i$$$ 单元格的坐标。您不得将同一个单元翻转两次。 请注意,您不能反转单元格 $$$(1, 1)$$$ 和 $$$(n, n)$$$。

示例

输入 #1

3
4
S010
0001
1000
111F
3
S10
101
01F
5
S0101
00000
01111
11111
0001F

输出 #1

1
3 4
2
1 2
2 1
0

注意

对于第一个测试用例,反转单元格后,我们得到以下网格: