SZ#G4M23. 【GESP强化 四级】TaK 标记

提交1 通过1
通过率100%
时间限制1000ms
内存限制256MiB
    ID: 11206 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 普及 上传者: 标签>GESPGESP强化C++c++编程题二维数组二维字符数组固定模板匹配

题目描述

刘老师要在一幅 N×MN\times M 的黑白字符图中寻找一种固定的 9×99\times9 “TaK 标记”。一个 9×99\times9 区域符合标记,当且仅当:左上角的 3×33\times3 全为 #,其正下方一行的前四格和正右方一列的前四格全为 .;右下角的 3×33\times3 全为 #,其正上方一行的后四格和正左方一列的后四格全为 .。标记内其他没有被指定的位置可以是任意字符,标记不旋转。

需要按左上角行号从小到大、同一行内列号从小到大的顺序,列出图中所有符合条件的 9×99\times9 区域左上角坐标。

输入格式

第一行输入两个整数 N,MN,M

接下来 NN 行,每行一个长度为 MM、只含 #. 的字符串。

输出格式

每找到一个 TaK 标记,就输出一行两个整数,表示其左上角行号和列号。若没有标记,不输出任何内容。

19 18
###......###......
###......###......
###..#...###..#...
..............#...
..................
..................
......###......###
......###......###
......###......###
.###..............
.###......##......
.###..............
............###...
...##.......###...
...##.......###...
.......###........
.......###........
.......###........
........#.........
1 1
1 10
7 7
10 2
9 21
###.#...........#.###
###.#...........#.###
###.#...........#.###
....#...........#....
#########...#########
....#...........#....
....#.###...###.#....
....#.###...###.#....
....#.###...###.#....
1 1
18 18
######............
######............
######............
######............
######............
######............
..................
..................
..................
..................
..................
..................
............######
............######
............######
............######
............######
............######

样例解释

  • 样例 1 中只有一个 9×99\times9 区域满足两组黑色方块及其白色边界要求。
  • 样例 2 中有多个符合条件的位置,按行优先顺序逐行输出。
  • 样例 3 没有任何符合要求的区域,因此输出为空。

数据范围与约定

  • 9N,M1009 \le N,M \le 100