蒟蒻求助p2324骑士精神
  • 板块题目总版
  • 楼主KMSK
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/10/18 02:01
  • 上次更新2023/11/4 03:25:35
查看原帖
蒟蒻求助p2324骑士精神
472423
KMSK楼主2021/10/18 02:01

我检查了代码感觉没问题,但是连样例都过不了,求助哪里没写对(广度优先搜索加Set判重) 代码如下,请神犇过目

#include<algorithm>
#include<set> 
using namespace std;
char a[7][7];
//set去重判定
set<string> se;
int t;
int p=0;
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
int x,y;
int ans=-1;
string an="111110111100*110000100000";//目标状态 
string getss()
{
	string ss="";
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=5;j++)
		ss+=a[i][j];
	}
	return ss; 
}
bool judge()
{
	string sk="";
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=5;j++)
		sk+=a[i][j];
	}
	//cout<<sk<<endl;
	if(sk==an)return true;
	return false;
	 
}
void bfs(int i,int j,int m)//步数 
{
	if(m>=15)return;
		
		if(judge())
			{
			    ans=m;
			    return;
		}
	for(int k=0;k<8;k++)
	{ 
		int ii=i+dx[k];
		int jj=j+dy[k];
		
		if(ii<1||ii>5||jj<1||jj>5)continue; 
		
		swap(a[ii][jj],a[i][j]);
		
		string s=getss();
		if(se.count(s)!=1)//目标状态未出现过就开始搜索 
		{
		se.insert(s);
		bfs(ii,jj,m+1);//增加步数,刷新空位 
	}
	 swap(a[ii][jj],a[i][j]); //如果出现过就换回来 
	 } 
}
int main()
{
	cin>>t;
	while(p<t)
	{
		p+=1;
		string sm="";
		for(int i=1;i<=5;i++)
		{
			cin>>sm;
			for(int j=1;j<=5;j++)
			{
				a[i][j]=sm[j-1];
				if(a[i][j]=='*')
				{
					x=i;
					y=j;
				}
			}
		}
	        bfs(x,y,0);
			cout<<ans<<endl;
			ans=-1;
	}
	return 0;
}
2021/10/18 02:01
加载中...