AT_abc302_b [ABC302B] Find snuke

题目描述

给你一个 $H$ 行 $W$ 列的字符矩阵。请你在当中的行列或者 $45\degree$ 斜上的八个方向上寻找连续的五个字符 `s`,`n`,`u`,`k`,`e`,并依次输出它们的位置。保证有且仅有一组解。

输入格式

第一行 $2$ 个整数 $H,W$。 接下来 $H$ 行每行一个长度为 $W$ 的字符串。

输出格式

共五行,每行两个整数,依次表示找到的 `s`,`n`,`u`,`k`,`e` 的坐标。

说明/提示

### 制約 - $ 5\leq\ H\leq\ 100 $ - $ 5\leq\ W\leq\ 100 $ - $ H,W $ は整数 - $ S_i $ は英小文字のみからなる長さ $ W $ の文字列 - 与えられるマス目の中に条件をみたす場所がただ $ 1 $ つ存在する ### Sample Explanation 1 この時、$ (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} $ は辺を共有しており、 各マスの中心は一直線上に存在するため、条件をみたしています。 !\[\](https://img.atcoder.jp/abc302/f0a6b1007df7fb00caa27a5f82a3afb1.png) ### Sample Explanation 2 $ (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 $ つめの条件をみたしていません。