/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
H 行 W 列のグリッドがあります。グリッドの各マスには英小文字が書かれており、上から i 行目、左から j 列目に書かれた文字は与えられる文字列 S_i の j 文字目と一致します。
英小文字 c_1,c_2 が与えられます。グリッドで文字 c_1 が書かれたマスと文字 c_2 が書かれたマスが辺で接する場所が存在するか判定してください。
より厳密には、以下の条件を満たす正整数の組 (h_1,w_1,h_2,w_2) が存在するか判定してください。
- 1\le h_1,h_2\le H
- 1\le w_1,w_2\le W
- グリッドの上から h_1 行目、左から w_1 列目に書かれた文字は c_1 である。
- グリッドの上から h_2 行目、左から w_2 列目に書かれた文字は c_2 である。
- |h_1-h_2|+|w_1-w_2|=1
制約
- 1\le H,W\le 10
- H,W は整数
- c_1,c_2 は英小文字
- S_1,S_2,\ldots,S_H は英小文字からなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W c_1 c_2 S_1 S_2 \vdots S_H
出力
グリッドで文字 c_1 と c_2 が辺で接する場所が存在するならば Yes を、存在しないならば No を出力せよ。
入力例 1
3 3 a t abc xtc qad
出力例 1
Yes
上から 3 行目、左から 2 列目に a が書かれており、上から 2 行目、左から 2 列目に t が書かれています。これらのマスは隣接しているので、 Yes を出力してください。
入力例 2
4 3 x r xxx xxb kkr rrr
出力例 2
No
x と r が隣接している場所は存在しないので、 No を出力してください。
入力例 3
5 5 n x iaamg krwwu nzyxc sgrnt mmjip
出力例 3
Yes
Problem Statement
You are given a grid with H rows and W columns. Each cell contains a lowercase English letter; the letter in the cell at row i (counted from the top) and column j (from the left) is the j-th character of the given string S_i.
Given lowercase English letters c_1 and c_2, determine if the grid has a pair of cells that share a side, containing letters c_1 and c_2.
More precisely, determine if there is a tuple of positive integers (h_1,w_1,h_2,w_2) such that:
- 1\le h_1,h_2\le H
- 1\le w_1,w_2\le W
- The cell in row h_1 and column w_1 contains the letter c_1.
- The cell in row h_2 and column w_2 contains the letter c_2.
- |h_1-h_2|+|w_1-w_2|=1
Constraints
- 1\le H,W\le 10
- H and W are integers.
- c_1 and c_2 are lowercase English letters.
- Each of S_1,S_2,\ldots,S_H is a string of length W, consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
H W c_1 c_2 S_1 S_2 \vdots S_H
Output
Print Yes if the grid has adjacent cells with the letters c_1 and c_2, and No otherwise.
Sample Input 1
3 3 a t abc xtc qad
Sample Output 1
Yes
The cell in row 3 and column 2 from the left contains a; the cell in row 2 and column 2 contains t. These cells share a side, so print Yes.
Sample Input 2
4 3 x r xxx xxb kkr rrr
Sample Output 2
No
There are no adjacent cells with x and r, so print No.
Sample Input 3
5 5 n x iaamg krwwu nzyxc sgrnt mmjip
Sample Output 3
Yes