← 返回题目列表

AtCoder · abc302_b

D. 寻找核弹

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

分数: 250 点

问题陈述

有一个网格 H 水平行和 W 垂直列。 每个单元格上都写有一个小写英文字母。 我们表示为 (i, j) 的单元格 i从顶部开始的第行和 j左起第 列。

写在网格上的字母表示为 H 字符串 S_1,S_2,\ldots, S_H,每个长度 W。 的 j第一个字母 S_i 代表写在 (i, j).

有一套独特的 连续单元格(垂直、水平或对角线) 在网格中 与 s, n, u, k,和 e 按此顺序写在上面。
找到此类单元格的位置并以输出部分中指定的格式打印它们。

五个单元格的元组 (A_1,A_2,A_3,A_4,A_5) 据说形成 一组 连续单元格(垂直、水平或对角线) 与 s, n, u, k,和 e 按此顺序写在上面 当且仅当满足以下所有条件时。

  • A_1,A_2,A_3,A_4 和 A_5 有字母 上面分别写着 s, n, u, k,和 e 。
  • 对于所有人 1\leq i\leq 4,细胞 A_i 和 A_{i+1} 共享一个角落或一侧。
  • 的中心 A_1,A_2,A_3,A_4,和 A_5 每隔一段时间就在一条公共线上。

约束

  • 5\leq H\leq 100
  • 5\leq W\leq 100
  • H 和 W 是整数。
  • S_i 是一个长度为 W 由小写英文字母组成。
  • 给定的网格具有唯一的一致单元格集。

输入

输入由标准输入按以下格式给出:

H W
S_1
S_2
\vdots
S_H

输出

按以下格式打印五行。

让 (R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5) 是所寻找集合中的单元格 上面分别写着 s, n, u, k,和 e 。 的 i- 第行应包含 R_i 和 C_i 按此顺序,用空格分隔。

换句话说,按以下格式打印它们:

R_1 C_1
R_2 C_2
\vdots
R_5 C_5

另请参阅下面的示例输入和输出。


示例输入 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

示例输出 1

5 2
5 3
5 4
5 5
5 6

元组 (A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) 满足条件。
确实,上面写的字母是 s, n, u, k,和 e;
对于所有人 1\leq i\leq 4,细胞 A_i 和 A_{i+1} 分享一面;
和单元格的中心位于同一直线上。


示例输入 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

示例输出 2

5 5
4 4
3 3
2 2
1 1

元组 (A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) 满足条件。
然而,例如, (A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) 违反了第三个条件,因为单元的中心不在同一直线上,尽管它满足第一个和第二个条件。


示例输入 3

10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk

示例输出 3

9 3
8 3
7 3
6 3
5 3