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 区域满足两组黑色方块及其白色边界要求,左上角坐标依次为 (1,1)(1,1)、(1,10)(1,10)、(7,7)(7,7)、(10,2)(10,2)。
  • 样例 2 中只有一个符合条件的区域,左上角坐标为 (1,1)(1,1)。
  • 样例 3 没有任何符合要求的区域,因此输出为空。

数据范围与约定

  • 9≤N,M≤1009 \le N,M \le 100