103022: [Atcoder]ABC302 C - Almost Equal

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:18 Solved:0

Description

Score : $250$ points

Problem Statement

You are given $N$ strings $S_1,S_2,\dots,S_N$, each of length $M$, consisting of lowercase English letter. Here, $S_i$ are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings $T_1,T_2,\dots,T_N$ such that:

  • for all integers $i$ such that $1 \le i \le N-1$, one can alter exactly one character of $T_i$ to another lowercase English letter to make it equal to $T_{i+1}$.

Constraints

  • $2 \le N \le 8$
  • $1 \le M \le 5$
  • $S_i$ is a string of length $M$ consisting of lowercase English letters. $(1 \le i \le N)$
  • $S_i$ are pairwise distinct.

Input

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

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

Output

Print Yes if one can obtain a conforming sequence; print No otherwise.


Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.


Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.


Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Input

题意翻译

### 题目描述 给定 $ N $ 个长度为 $ M $ 的仅包含小写英文字母的字符串 $ S_1, S_2, \cdots, S_N $。保证 $ S_i $ 互不相同。 判断是否可以通过对这些字符串重新排序,得到一个新的字符串序列 $ T_1, T_2, \cdots, T_N $,使得: - 对于任意 $ i $ 使得 $ 1 \le i \le N - 1 $,均满足 $ T_i $ 在改变**恰好一个**字母后可以等于 $ T_{i + 1} $。 ### 数据范围 - $ 2 \le N \le 8 $ - $ 1 \le M \le 5 $ - 保证 $ S_i $ 长度为 $ M $,且仅由小写英文字母组成。$ (1 \le i \le N) $ - 保证 $ S_i $ 互不相同。 ### 样例一解释 安排顺序如下:`abcd`,`abed`,`bbed`,`fbed`。满足条件。 ### 样例二解释 无论如何对这两个字符串排序,均不可能满足条件。

Output

分数:250分

问题描述

你将得到$N$个长度为$M$的字符串$S_1,S_2,\dots,S_N$,每个字符串由小写英文字母组成。这里,$S_i$两两不同。

确定是否可以重新排列这些字符串,得到一个新的字符串序列$T_1,T_2,\dots,T_N$,满足以下条件:

  • 对于所有满足$1 \le i \le N-1$的整数$i$,可以将$T_i$中的一个字符改为另一个小写英文字母,使其等于$T_{i+1}$。

约束

  • $2 \le N \le 8$
  • $1 \le M \le 5$
  • $S_i$是一个长度为$M$的字符串,由小写英文字母组成。 $(1 \le i \le N)$
  • $S_i$两两不同。

输入

输入从标准输入以以下格式给出:

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出

如果可以得到一个符合条件的序列,打印Yes;否则打印No


样例输入1

4 4
bbed
abcd
abed
fbed

样例输出1

Yes

可以按照这个顺序重新排列它们:abcdabedbbedfbed。这个序列满足条件。


样例输入2

2 5
abcde
abced

样例输出2

No

无论字符串如何重新排列,条件永远不会得到满足。


样例输入3

8 4
fast
face
cast
race
fact
rice
nice
case

样例输出3

Yes

HINT

n个长度为m的单词,是否可以接成一条龙,使得相邻两个单词仅有一个字母不同?

加入题单

上一题 下一题 算法标签: