AT_abc302_c

题意

有 \(n\) 个字符串，它们的长度都为 \(m\)。问能否通过改变它们的顺序，使得后一个字符串能由前一个字符串只改变一个字母而得到？

思路

本题数据范围 $ 2 \le N \le 8 $，非常小，因此可以考虑全排列枚举所有的情况，最后检验是否存在符合要求的顺序即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

string s[101],c[101];
int a[101],n,m,pd;

void dfs( int k )
{
	for( int i = 1 ; i <= n ; i ++ )
	{
		if( a[i] == 0 )
		{
			a[i] = 1;
			c[k] = s[i];
			if( k == n )
			{
				int fg = 0,cnt = 0;
				for( int j = 1 ; j < n ; j ++ )
				{
					cnt = 0;
					for( int k = 0 ; k < m ; k ++ )
						if( c[j][k] != c[j + 1][k] )
							cnt ++;
					if( cnt != 1) fg = 1;
				}
				if( !fg ) pd = 1;
			}
			else dfs( k + 1 );
			a[i] = 0;
			c[k] = "";
		}
	}
}

int main()
{
	cin >> n >> m;
	for( int i = 1 ; i <= n ; i ++ )
		cin >> s[i];
	dfs(1);
	if( pd ) cout << "Yes";
	else cout << "No";
	return 0;
}