目前在洛谷WA,在vjudge OJ的这一题(需要登录)里仅拿到部分分 (31/41)
代码全部加了注释,方便大家理解思路。题目描述检查过了,没有理解错误。我还试图打印调试查找问题,一无所获(我在14-15行、27-28行、29-30行、38-39行之间输出了)。
我认为思路是没有问题的,请重点检查下我的实现细节。
谢谢!
#include <iostream>
#include <string>
using namespace std;
string a[10];//存储输入的数组
string s[10];//记录递归排列的数组
bool vis[10];
int n,m;//N 个长度 M 的字符串
bool ans;//答案:能不能组成题目所述的序列
bool chk(string now,string target)
{
int count=0;//两个字符串不相同的字符的数量(如果数量为1,证明只需要改动一个)
for(int i=1;i<=m;i++)//遍历整个字符串
{
if(now[i]!=target[i]) count++;//如果不一样 count++
}
if(count!=1) return false;//如果不是只有1个不一样,那就不符合要求
return true;//否则符合要求
}
void dfs(int len)
{
if(ans) return;//如果已经找到解法 那就不用继续搜了
if(len>n)//如果搜到头
{
bool flag=true;//先设定为true,如果待会都没有返回false,那就是true
for(int i=1;i<n;i++)//循环到n-1防止越界
{
if(!chk(s[i],s[i+1])) flag=false;//只要有一个不行,那这个排列就不行
}
ans=flag;//如果这个不行,那ans还是false,反之亦然
return;
}
for(int i=1;i<=n;i++)//遍历全排列
{
if(!vis[i])//如果没访问过
{
vis[i]=1;//标记为访问
s[len]=a[i];//s数组当前元素为i
dfs(len+1);//深搜
vis[i]=0;//恢复
}
}
}
int main()
{
cin>>n>>m;//输入
for(int i=1;i<=n;i++) cin>>a[i];
dfs(1);//从第1个开始深搜
if(ans) cout<<"Yes";//如果可以,那么输出yes
else cout<<"No";//否则no
return 0;
}