Find snuke

题目描述

有一个由 $H$ $Horizontal$ 行和 $W$ $Vertical$ 列组成的网格。每个格子上都写有一个小写英文字母。 我们用 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。 网格上写的字母由 $H$ 个字符串 $S_1,S_2,\ldots, S_H$ 表示，每个长度为 $W$。 $S_i$ 的第 $j$ 个字母表示写在 $(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$ 的中心点位于一条公线且间隔相等。

输入格式

输入从标准输入给出，格式如下： $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$

另请参见下面的样例输入输出。

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

5 2
5 3
5 4
5 5
5 6

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

5 5
4 4
3 3
2 2
1 1

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

9 3
8 3
7 3
6 3
5 3

提示

$5\leq H\leq 100$ $5\leq W\leq 100$ $H$ 和 $W$ 是整数。 $S_i$ 是一个长度为 $W$ 的由小写英文字母组成的字符串。 给定的网格保证存在且唯一符合条件的一组格子。元组 $(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}$ 共享一条边；
并且这些格子的中心点在同一条直线上。 <img ,="" src="https://img.atcoder.jp/abc302/f0a6b1007df7fb00caa27a5f82a3afb1.png" width="400"/>
元组 $(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))$ 违反了第三个条件，因为这些格子的中心点不在同一条直线上，尽管它满足第一个和第二个条件。

标签: AtCoder|abc302B

来源

AtCoder|abc302B