eight（待考究）

为什么明明结果都可以到达那种情况，步骤不一样就不给通过

QAQ

有哪位大佬提点一下，在下感激不尽~~~

我的代码：

#include <iostream>
#include <queue>
#include <cstdio>
#include <string>
using namespace std;
int per[10]={1,1,2,6,24,120,720,5040,40320,362880};
int start[9],finish[9]={1,2,3,4,5,6,7,8,0};
bool dir[362880]={0};
int way[4][2]={0,1,1,0,0,-1,-1,0};
char owo[4]={ 'd','r','u' ,'l' };
class state{
public:
int position[9];
string step;
state(int arr[],string ss):step(ss){
for(int i=0;i<9;i++)position[i]=arr[i];
}
state(){}
};
bool cantor(int str[],int n){
int result=0;
for(int i=0;i<n;i++){
int counted=0;
for(int j=i+1;j<n;j++){
if(str[i]>str[j]){
counted++;
}
}
result+=counted*per[n-i-1];
}
if(!dir[result]){
dir[result]=1;
return 1;
}
return 0;
}
bool judge(int arr1[],int arr2[]){
for(int i=0;i<9;i++)
if(arr1[i]!=arr2[i])return 0;
return 1;
}
void bfs(){
queue<state> que;
que.push(state(start,string()));
cantor(start,9);
state now;
while(!que.empty()){
now=que.front();
que.pop();
int x,y,z,tx,ty,tz;//z为元素中0的位置,x,y为转化成图形第几行第几列
for(z=0;z<9;z++)
if(now.position[z]==0)
break;
x=z%3;
y=z/3;
for(int i=0;i<4;i++){
tx=x+way[i][0];
ty=y+way[i][1];
if(tx>=0&&tx<3&&ty<3&&ty>=0){
char tstep=owo[i];
tz=ty*3+tx;
swap(now.position[tz],now.position[z]);
if(judge(now.position,finish)){
cout << now.step+tstep << endl;
return;
}
if(cantor(now.position,9))
que.push(state(now.position,now.step+tstep));
swap(now.position[tz],now.position[z]);
}
}
}
cout << "unsolvable" << endl;
}
int main()
{
int i;
char ch,_,__;
for(i=0;i<9;i++){
if(i!=8)scanf("%c%c%c",&ch,&_,&__);
else scanf("%c",&ch);
if(ch=='x')start[i]=0;
else start[i]=ch-'0';
}
//for(i=0;i<9;i++)printf("%d\n",start[i]);
//for(i=0;i<9;i++)scanf("%d",&finish[i]);
bfs();
return 0;
}

然后一下代码用来验证：

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main(){
string str;
char QAQ[9],_,__;
int way[4][2]={1,0,0,1,-1,0,0,-1};
char owo[4]={'r','d','l','u'};
for(int i=0;i<9;i++){
if(i<8)scanf("%c%c%c",&QAQ[i],&_,&__);
else scanf("%c",&QAQ[i]);
}
cin >> str;
int j;
for(j=0;j<9;j++){
if(QAQ[j]=='x')break;
}
int x,y,z=j,tx,ty,tz;
//for(string::iterator ite=str.begin();ite!=str.end();ite++)
for(j=0;j<str.size();j++)
{
x=z%3;
y=z/3;
for(int i=0;i<4;i++){
if(str[j]==owo[i]){//ite
tx=x+way[i][0];
ty=y+way[i][1];
if(tx>=0&&tx<3&&ty>=0&&ty<3){
tz=ty*3+tx;
swap(QAQ[z],QAQ[tz]);
z=tz;
break;
}
}
}
}
for(int i=0;i<9;i++)printf("%c ",QAQ[i]);
return 0;
}

原文链接:https://www.cnblogs.com/sos3210/p/12292116.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有