蒟蒻求助:WA on test 1
查看原帖
蒟蒻求助:WA on test 1
1073879
Karl_Wan楼主2024/7/30 19:09

目前在洛谷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;
}
2024/7/30 19:09
加载中...