← 返回题目列表

AtCoder · abc312_b

D. TaK 代码

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

分数: 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代码条件的区域。