← 返回题目列表

AtCoder · past23_d

D. 字符相邻

中文机器翻译题面 查看原题

问题陈述

给你一个网格 H 行和 W 列。 每个单元格包含一个小写英文字母;行单元格中的字母 i (从顶部算起)和列 j (从左起)是 j- 给定字符串的第一个字符 S_i.

给定小写英文字母 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

输出

打印 Yes 如果网格具有带有字母的相邻单元格 c_1 和 c_2,和 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