B - Find snuke 解説 /

実行時間制限: 2 sec / メモリ制限: 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

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

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

入力例 3

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

出力例 3

9 3
8 3
7 3
6 3
5 3

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 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Sample Output 1

5 2
5 3
5 4
5 5
5 6

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 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Sample Output 2

5 5
4 4
3 3
2 2
1 1

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 3

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

Sample Output 3

9 3
8 3
7 3
6 3
5 3