分数: 200 点
问题陈述
高桥发明了 Tak Code,一种二维码。 TaK 代码满足以下所有条件:
- 它是由九个水平行和九个垂直列组成的区域。
- 所有 18 左上角和右下角三乘三区域中的单元格为黑色。 与左上角或右下角的 3×3 区域相邻(水平、垂直或对角)的
- 所有 14 单元格为白色。
不允许轮换 TaK 代码。
给你一个网格 N 水平行和 M 垂直列。
网格状态描述为 N 字符串, S_1,\ldots,和 S_N,每个长度 M。 牢房位于 i从顶部开始的第行和 j如果左侧的第 列是黑色 j- 第一个字符 S_i is #,如果是白色 ..
找到完全包含在网格中且满足 TaK 代码条件的所有 9×9 区域。
约束
- 9 \leq N,M \leq 100
- N 和 M 是整数。
- S_i 是一个长度为 M 组成
.和#.
输入
输入由标准输入按以下格式给出:
N M S_1 \vdots S_N
输出
对于所有对 (i,j) 这样九乘九的区域,其左上角的单元格位于 i从顶部开始的第行和 j左起第 列,满足 TaK Code 的条件,打印一行包含 i、一个空格,以及 j 按此顺序。
这些对必须按字典升序排序;也就是说, i 必须按升序排列,并且在同一范围内 i, j 必须按升序排列。
示例输入 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
示例输出 1
1 1 1 10 7 7 10 2
TaK 代码如下所示,其中 # 是黑色单元格, . 是一个白细胞,并且 ? 可以是黑色或白色。
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
在输入给出的网格中,九乘九的区域,其左上角的单元格位于 10从顶部开始的第行和 2-左起第2列,满足TaK Code的条件,如下所示。
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
示例输入 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
示例输出 2
1 1
示例输入 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
示例输出 3
可能没有满足TaK代码条件的区域。