数据结构描述
typedef struct node {
int a[3][3];
struct node *pre;
int x,y;
} *Pnode,Node;
a数组存放该节点的状态
pre指针指向该节点的父节点
queue<Pnode> open;
open表是一个先进先出的队列
问题是否有解的判断
//判断是否有解
int a[9],b[9];
for(int i=0; i<9; i++) {
a[i]=Phead->a[i/3][i%3] ;
b[i]=target[i/3][i%3];
}
int t1=0,t2=0;
for(int i=8; i>=0; i--)
for(int j=i-1; j>=0; j--) {
if(a[i]!=0)
if(a[i]<a[j])
t1++;
if(b[i]!=0)
if(b[i]<b[j])
t2++;
}
printf("逆序数N1=%d 逆序数N2=%d\n",t1,t2);
if(t1%2!=t2%2) {
printf("该问题无解");
return 0;
}
其实状态和目标状态必须同为奇序列或同为偶序列(0不加入计算)
源代码
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<cstring>
using namespace std;
typedef struct node {
int a[3][3];
struct node *pre;
int x,y;
} *Pnode,Node;
int Check(Pnode tem);
void bfs();
void up(Pnode tem);
void Right(Pnode ptm);
void Left(Pnode ptm);
void Down(Pnode ptm);
void Up(Pnode ptm);
void show(Pnode tem);
Pnode Phead;
queue<Pnode> open;
int flag=0;
int target[3][3]= {3,6,8,2,5,7,0,1,4};
int main() {
Phead =(Pnode)malloc(sizeof(Node));
Phead->pre =NULL;
printf("请输入当前状态:\n");
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) {
scanf("%d",&Phead->a[i][j]);
if(Phead->a[i][j]==0) {
Phead->x=i;
Phead->y=j;
}
}
printf("请输入目标:\n");
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) scanf("%d",&target[i][j]);
//判断是否有解
int a[9],b[9];
for(int i=0; i<9; i++) {
a[i]=Phead->a[i/3][i%3] ;
b[i]=target[i/3][i%3];
}
int t1=0,t2=0;
for(int i=8; i>=0; i--)
for(int j=i-1; j>=0; j--) {
if(a[i]!=0)
if(a[i]<a[j])
t1++;
if(b[i]!=0)
if(b[i]<b[j])
t2++;
}
printf("逆序数N1=%d 逆序数N2=%d\n",t1,t2);
if(t1%2!=t2%2) {
printf("该问题无解");
return 0;
}
bfs();
return 0;
}
void bfs() {
open.push(Phead);
Check(Phead);
while(!open.empty()&&flag==0) {
Pnode tem=open.front();
if(flag==0)
Up(tem);
if(flag==0)
Down(tem);
if(flag==0)
Left(tem);
if(flag==0)
Right(tem);
open.pop();
}
}
void Up(Pnode ptm) {
Pnode tem= (Pnode)malloc(sizeof(Node));
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) tem->a[i][j]=ptm->a[i][j];
tem->x=ptm->x;
tem->y=ptm->y;
int x=ptm->x,y=ptm->y;
if(x==0) return ;
int t=tem->a[x][y];
tem->a[x][y]=tem->a[x-1][y] ;
tem->a[x-1][y]=t;
tem->x=x-1;
int n=1;
int index=0;
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) {
index+=tem->a[i][j]*n;
n=n*10;
}
tem->pre=ptm;
if(Check(tem)==0) {
open.push(tem);
}
}
void Down(Pnode ptm) {
Pnode tem= (Pnode)malloc(sizeof(Node));
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) tem->a[i][j]=ptm->a[i][j];
tem->x=ptm->x;
tem->y=ptm->y;
int x=ptm->x,y=ptm->y;
if(x==2) return ;
int t=tem->a[x][y];
tem->a[x][y]=tem->a[x+1][y] ;
tem->a[x+1][y]=t;
tem->x=x+1;
int n=1;
int index=0;
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) {
index+=tem->a[i][j]*n;
n=n*10;
}
tem->pre=ptm;
if(Check(tem)==0) {
open.push(tem);
}
}
void Left(Pnode ptm) {
Pnode tem= (Pnode)malloc(sizeof(Node));
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) tem->a[i][j]=ptm->a[i][j];
tem->x=ptm->x;
tem->y=ptm->y;
int x=ptm->x,y=ptm->y;
if(y==0) return ;
int t=tem->a[x][y];
tem->a[x][y]=tem->a[x][y-1] ;
tem->a[x][y-1]=t;
tem->y=y-1;
int n=1;
int index=0;
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) {
index+=tem->a[i][j]*n;
n=n*10;
}
tem->pre=ptm;
if(Check(tem)==0) {
open.push(tem);
}
}
void Right(Pnode ptm) {
Pnode tem= (Pnode)malloc(sizeof(Node));
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) tem->a[i][j]=ptm->a[i][j];
tem->x=ptm->x;
tem->y=ptm->y;
int x=ptm->x,y=ptm->y;
if(y==2) return ;
int t=tem->a[x][y];
tem->a[x][y]=tem->a[x][y+1] ;
tem->a[x][y+1]=t;
tem->y=y+1;
int n=1;
int index=0;
for(int i=0; i<3; i++)
for(int j=0; j<3; j++) {
index+=tem->a[i][j]*n;
n=n*10;
}
tem->pre=ptm;
if(Check(tem)==0) {
open.push(tem);
}
}
int Check(Pnode tem) {
for(int i=0; i<3; i++)
for(int j=0; j<3; j++)
if(tem->a[i][j]!=target[i][j]) {
// printf("falg=%d\n",flag);
return 0;
}
flag=1;
while(tem!=NULL&&flag==1) {
show(tem);
tem=tem->pre;
//free(tem);
}
printf("找到解|");
return 1;
}
void show(Pnode tem) {
printf("---------\n");
for(int i=0; i<3; i++) {
for(int j=0; j<3; j++)
printf("%d ",tem->a[i][j]);
printf("\n");
}
printf("---------\n");
}
网友评论