B - Find snuke

Contest Duration: 2023-05-20(Sat) 12:00 - 2023-05-20(Sat) 13:40 (local time) (100 minutes) Back to Home

B - Find snuke Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $250$ 点

問題文

縦 $H$ マス $\times$ 横 $W$ マスのマス目があり、各マスに $1$ つずつ英小文字が書き込まれています。上から $i$ 行目かつ左から $j$ 列目のマスを $(i,j)$ で表します。

マス目に書き込まれている英小文字は $H$ 個の長さ $W$ の文字列 $S_1,S_2,\ldots, S_H$ によって与えられ、 $S_i$ の $j$ 文字目が、 $(i, j)$ に書き込まれた英小文字を表します。

マス目の中に、s, n, u, k, e が この順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる 場所がただ $1$ つ存在します。
そのような場所を見つけ、そのマスの位置を出力の形式に従って出力してください。

ただし、s, n, u, k, e が この順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる場所とは、 $5$ つのマスの組 $(A_1,A_2,A_3,A_4,A_5)$ であって、次をすべてみたすものをさします。

$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$ の文字列
与えられるマス目の中に条件をみたす場所がただ $1$ つ存在する

入力

入力は以下の形式で標準入力から与えられる。

 $H$   $W$ 
 $S_1$ 
 $S_2$ 
 $\vdots$ 
 $S_H$

出力

次の形式にしたがって、 $5$ 行出力せよ。

条件をみたす場所のうち s, n, u, k, e が書かれたマスがそれぞれ $(R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5)$ であるとき、 $i$ 行目には $R_i$ と $C_i$ をこの順に空白区切りで出力せよ。

すなわち、以下のように出力せよ。

 $R_1$   $C_1$ 
 $R_2$   $C_2$ 
 $\vdots$ 
 $R_5$   $C_5$

以下の入力例も参考にせよ。

入力例 1Copy

Copy

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

出力例 1Copy

Copy

この時、 $(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}$ は辺を共有しており、
各マスの中心は一直線上に存在するため、条件をみたしています。

入力例 2Copy

Copy

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

出力例 2Copy

Copy

$(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))$ は、 $1,2$ つめの条件をみたしていますが、
マスの中心が一直線上に存在しないため、 $3$ つめの条件をみたしていません。

入力例 3Copy

Copy

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

出力例 3Copy

Copy

Score : $250$ points

Problem Statement

There is a grid with $H$ horizontal rows and $W$ vertical columns. Each cell has a lowercase English letter written on it. We denote by $(i, j)$ the cell at the $i$ -th row from the top and $j$ -th column from the left.

The letters written on the grid are represented by $H$ strings $S_1,S_2,\ldots, S_H$ , each of length $W$ . The $j$ -th letter of $S_i$ represents the letter written on $(i, j)$ .

There is a unique set of contiguous cells (going vertically, horizontally, or diagonally) in the grid with s, n, u, k, and e written on them in this order.
Find the positions of such cells and print them in the format specified in the Output section.

A tuple of five cells $(A_1,A_2,A_3,A_4,A_5)$ is said to form a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order if and only if all of the following conditions are satisfied.

$A_1,A_2,A_3,A_4$ and $A_5$ have letters s, n, u, k, and e written on them, respectively.
For all $1\leq i\leq 4$ , cells $A_i$ and $A_{i+1}$ share a corner or a side.
The centers of $A_1,A_2,A_3,A_4$ , and $A_5$ are on a common line at regular intervals.

Constraints

$5\leq H\leq 100$
$5\leq W\leq 100$
$H$ and $W$ are integers.
$S_i$ is a string of length $W$ consisting of lowercase English letters.
The given grid has a unique conforming set of cells.

Input

The input is given from Standard Input in the following format:

 $H$   $W$ 
 $S_1$ 
 $S_2$ 
 $\vdots$ 
 $S_H$

Output

Print five lines in the following format.

Let $(R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5)$ be the cells in the sought set with s, n, u, k, and e written on them, respectively. The $i$ -th line should contain $R_i$ and $C_i$ in this order, separated by a space.

In other words, print them in the following format:

 $R_1$   $C_1$ 
 $R_2$   $C_2$ 
 $\vdots$ 
 $R_5$   $C_5$

See also Sample Inputs and Outputs below.

Sample Input 1Copy

Copy

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Sample Output 1Copy

Copy

Tuple $(A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6))$ satisfies the conditions.
Indeed, the letters written on them are s, n, u, k, and e;
for all $1\leq i\leq 4$ , cells $A_i$ and $A_{i+1}$ share a side;
and the centers of the cells are on a common line.

Sample Input 2Copy

Copy

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Sample Output 2Copy

Copy

Tuple $(A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1))$ satisfies the conditions.
However, for example, $(A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1))$ violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.

Sample Input 3Copy

Copy

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

Sample Output 3Copy

Copy