no_aid.cpp

九宫图盲目扫描算法

//=================================
//盲目搜索算法
//=================================
#include<iostream>
#include<fstream>
#include<sstream>
using namespace std;
//----------------------------------
typedef int Mat[3][3];//定义3*3数组类型
Mat wxf,aid;
int n=0,nn=0;
int p=0,num=0;
typedef struct Node{
	Mat c;//存储每一步的结点矩阵
	int noway[4];//可以走的路线l,u,r,d
	int father;//指向父亲节点
}Node;//结点结构
typedef struct path{
	Mat d;//存储矩阵
	int tag;
}path;//路径结构
Node result[40000];//保留分解的结点
path paths[10000];//保留解路径上的结点
void change(Mat a,Mat b);//完成两个数组的赋值（将数组b的值赋给数组a）
void input();//从文件读入初始状态
void output();//将解路径输出到文件
int compare(Mat a);//判断是否为目标节点
int slove(Mat a);//判断初始状态是否可解
void judge(Mat a);//判断移动路线
void movl(Mat a);//将0左移
void movr(Mat a);//将0右移
void movd(Mat a);//将0下移
void movu(Mat a);//将0上移
//----------------------------------
void main(){	
	input();
	if(!slove(wxf))
	{
		cout<<"不可解"<<endl;
		return;
	}
	change(result[n].c,wxf);
	result[n].father=-1;
	//设定初始允许移动方向
	judge(result[n].c);
	for(n=0;n<40000;n++)
	{
		if(nn>=39999)
		{
			for(int w=n;w<=nn;w++)
			{
				if(compare(result[w].c))
				{
					n=w;
					goto ww;
				}
			}
			cout<<"已扩展了40000个结点"<<endl;
			cout<<"虽然问题可解，但在范围内找不到目标结点"<<endl;
			return;
		}
		if(compare(result[n].c))
		{
ww:			while(n>=0)
			{
				change(paths[p].d,result[n].c);
				paths[p].tag=n;
				n=result[n].father;
				num++;
				p++;
			}
			output();
			return;
		}
		else
		{
			/*========分解节点=============*/
			if(result[n].noway[0])
			{
				movl(result[n].c);
			}
			if(result[n].noway[1])
			{
				movu(result[n].c);
			}
			if(result[n].noway[2])
			{
				movr(result[n].c);
			}
			if(result[n].noway[3])
			{
				movd(result[n].c);
			}
		}
	}
}
//----------------------------------
void input(){
	ifstream startin("start.txt");
	int sj,si=0;
	for(string ss;getline(startin,ss);)
	{
		sj=0;
		istringstream sin(ss);
		for(int ia;sin>>ia;)
		{	
			wxf[si][sj]=ia;
			sj++;
		}
		si++;
	}
	ifstream endin("end.txt");
	int ei=0,ej;
	for(string es;getline(endin,es);)
	{
		ej=0;
		istringstream sin(es);
		for(int ib;sin>>ib;)
		{	
			aid[ei][ej]=ib;
			ej++;
		}
		ei++;
	}
}
//----------------------------------
int compare(Mat a){
	int m=0,mm=0,k=0;
	for(m=0;m<3;m++)
	{
		for(mm=0;mm<3;mm++)
		{
			if(a[m][mm]!=aid[m][mm])
				return 0;
		}
	}
	return 1;
}
//----------------------------------
void movl(Mat a){
	change(wxf,a);
	nn++;
	int i=0,j;
	for(;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(wxf[i][j]==0)
				goto movl;
		}
	}
movl:wxf[i][j]=wxf[i][j-1];
	wxf[i][j-1]=0;
	change(result[nn].c,wxf);
	judge(result[nn].c);
	result[nn].father=n;
	result[nn].noway[2]=0;
}
//-----------------------------------
void movr(Mat a){
	change(wxf,a);
	nn++;
	int i=0,j;
	for(;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(wxf[i][j]==0)
				goto movr;
		}
	}
movr:
	wxf[i][j]=wxf[i][j+1];
	wxf[i][j+1]=0;
	change(result[nn].c,wxf);
	judge(result[nn].c);
	result[nn].father=n;
	result[nn].noway[0]=0;
}
//----------------------------------
void movd(Mat a){
	change(wxf,a);
	nn++;
	int i=0,j;
	for(;i<3;++i)
	{
		for(j=0;j<3;++j)
		{
			if(wxf[i][j]==0)
				goto movd;
		}
	}
movd:
	wxf[i][j]=wxf[i+1][j];
	wxf[i+1][j]=0;
	change(result[nn].c,wxf);
	judge(result[nn].c);
	result[nn].father=n;
	result[nn].noway[1]=0;
}
//---------------------------------
void movu(Mat a){
	change(wxf,a);
	nn++;
	int i=0,j;
	for(;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(wxf[i][j]==0)
				goto movu;
		}
	}
movu:
	wxf[i][j]=wxf[i-1][j];
	wxf[i-1][j]=0;
	change(result[nn].c,wxf);
	judge(result[nn].c);
	result[nn].father=n;
	result[nn].noway[3]=0;
}
//-----------------------------------
void judge(Mat a){
	int q=0,qq;
	for(;q<3;q++)
	{
		for(qq=0;qq<3;qq++)
		{
			if(a[q][qq]==0)
				goto movtag;
		}
	}
movtag:
	switch(q)//确定行号
	{
		case 0:
			{
				result[nn].noway[3]=1;
				result[nn].noway[1]=0;
				break;
			}
		case 2:
			{
				result[nn].noway[1]=1;
				result[nn].noway[3]=0;
				break;
			}
		default:
			{
				result[nn].noway[1]=1;
				result[nn].noway[3]=1;
				break;
			}
	}
	switch(qq)//确定列号
	{
		case 0:
			{
				result[nn].noway[2]=1;
				result[nn].noway[0]=0;
				break;
			}
		case 2:
			{
				result[nn].noway[0]=1;
				result[nn].noway[2]=0;
				break;
			}
		default:
			{
				result[nn].noway[2]=1;
				result[nn].noway[0]=1;
				break;
			}
	}
}
//---------------------------------------
void change(Mat a,Mat b)
{
	for(int e=0;e<3;e++)
		for(int ee=0;ee<3;ee++)
		{
			a[e][ee]=b[e][ee];
		}
}
//---------------------------------------
void output()
{
	ofstream out("path.txt");
	out<<"一共扩展出"<<nn<<"个结点"<<endl;
	for(p=num-1;p>=0;p--)
	{
		out<<"结点"<<paths[p].tag<<endl;
		int j,i=0;
		for(;i<3;i++)
		{
			for(j=0;j<3;j++)
			{
				out<<paths[p].d[i][j]<<" ";
			}
			out<<endl;
		}
		out<<"  ↓"<<endl;
	}
	out<<"正确的解路径"<<endl;
	out<<"解路径步数"<<num<<endl;
}
//---------------------------------
int slove(Mat a)
{
	int k=0,count=0;
	int intial[8];
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(a[i][j]!=0)
			{
				intial[k]=a[i][j];
				k++;
			}
			else
				continue;
		}
	}
	for(k=k-1;k>0;k--)
	{
		for(int kk=0;kk<=k;kk++)
		{
			if(intial[kk]<intial[k])
			{
				count++;
			}
			else
				continue;
		}
	}
	if(count%2)
		return 1;
	else
		return 0;
}