我检查了代码感觉没问题,但是连样例都过不了,求助哪里没写对(广度优先搜索加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;
}