TaK Code

题目描述

Takahashi 发明了一种名为 TaK Code 的二维码。一个 TaK Code 满足以下所有条件：

它是由九行九列构成的区域。 左上和右下的两个 3×3 区域中的所有 $18$ 个格子都是黑色的。 与左上或右下 3×3 区域相邻（横向、纵向或对角线方向）的所有 $14$ 个格子都是白色的。

不允许对 TaK Code 进行旋转。 给出一个有 $N$ 行 $M$ 列的网格。 该网格的状态由 $N$ 个字符串 $S_1,\ldots,S_N$ 描述，每个字符串的长度为 $M$。从上数第 $i$ 行、从左数第 $j$ 列的格子若对应 $S_i$ 的第 $j$ 个字符为 # 则为黑色，为 $.$ 则为白色。 找出所有完全包含在该网格内且满足 TaK Code 条件的 9×9 区域。

输入格式

输入从标准输入按照以下格式给出： $N$ $M$ $S_1$ $\vdots$ $S_N$

输出格式

对于所有满足 TaK Code 条件的以第 $i$ 行第 $j$ 列（从 1 开始计数）为左上角的 9×9 区域，按一行一个的格式输出 $i$、一个空格、$j$。
这些对需要按字典序升序排列；即先按 $i$ 升序，同一 $i$ 下按 $j$ 升序。

19 18
###......###......
###......###......
###..#...###..#...
..............#...
..................
..................
......###......###
......###......###
......###......###
.###..............
.###......##......
.###..............
............###...
...##.......###...
...##.......###...
.......###........
.......###........
.......###........
........#.........

1 1
1 10
7 7
10 2

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

###......
###......
###......
.........
..##.....
..##.....
......###
......###
......###

9 21
###.#...........#.###
###.#...........#.###
###.#...........#.###
....#...........#....
#########...#########
....#...........#....
....#.###...###.#....
....#.###...###.#....
....#.###...###.#....

1 1

提示

$9 \leq N,M \leq 100$ $N$ 和 $M$ 是整数。 $S_i$ 是长度为 $M$ 的由 $.$ 和 # 组成的字符串。TaK Code 的样子如下，其中 # 表示黑色格子，$.$ 表示白色格子，$?$ 可以是黑色或白色。

在输入给出的网格中，以从上数第 $10$ 行、第 $2$ 列为左上角的 9×9 区域满足 TaK Code 的条件，如下所示。
也可能没有满足 TaK Code 条件的区域。

标签: AtCoder|abc312B

来源

AtCoder|abc312B