puzz.cpp

重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事 “关羽义释曹操”而设计的智力玩具“华容道”

#include <iostream> 
#include <vector> 
#include <fstream>
#include <algorithm>
using   namespace   std;

int rowsz,boardsz,maxdep,*sour,*dest,*pos;


const int sth[4]={1,0,3,2};

class InitialBrd
{
	friend bool Tosolve(int dep,InitialBrd E);
public:
	vector<int> boardm;
	void GetBrd(int *m);
	bool Mvon(int dir);
	int heur(){return dist;}
	int Getdistance(const int &v,const int &loc);
	bool reached();
	int dir(){return (path.back());}
	void out();
private:
	int y,x;
	vector<char>path;
	int dist;
};

void InitialBrd::GetBrd(int *m)
{
	for(int i=0;i<boardsz;i++)
	{
		boardm.push_back(m[i]);
		if(m[i]==0)
		{
			y=i/rowsz;
			x=i%rowsz;
		}
	}
	for(i=0,dist=0;i<boardsz;i++)
	{
		if(boardm[i]!=0)
		{
			dist+=Getdistance(boardm[i],i);
		}
	}
}

//分别向三个不同的方向移动
bool InitialBrd::Mvon(int dir)
{
	const int step[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
	int nx=x+step[dir][0],ny=y+step[dir][1];
	if((path.empty()||sth[dir]!=(path.back()))&&nx>-1&&nx<rowsz&&ny>-1&&ny<rowsz)
	{
		dist=dist+1-Getdistance(boardm[ny*rowsz+nx],ny*rowsz+nx)+Getdistance(boardm[ny*rowsz+nx],y*rowsz+x);
		swap(boardm[y*rowsz+x],boardm[ny*rowsz+nx]);
		y=ny;
		x=nx;
		path.push_back(dir);
		return true;
	}
	else
		return false;
}

//计算距离
int InitialBrd::Getdistance(const int &v,const int &loc)
{
	int dis=abs((pos[v]%rowsz)-(loc%rowsz));
	dis+=abs((pos[v]/rowsz)-(loc/rowsz));
	return dis;
}

//目标状态的到达
bool InitialBrd::reached()
{
	for(int i=0;i<boardsz;i++)
		if(boardm[i]!=dest[i])
			return false;
	return true;
}

//输出结果

void InitialBrd::out()
{
	ofstream fout;

    fout.open("output.txt");  

	const char dir[]="UDLR";

	fout<<path.size()<<endl;
	for(int i=0;i<path.size();i++)
	{
		fout<<dir[path[i]];	
	}

	fout.close();
}


//深化的A*搜索算法IDASTAR描述如下
bool Tosolve(int dep,InitialBrd E)
{
	if(dep+E.dist<=maxdep)
	{
		if(E.reached()){E.out();return true;}
		for(int i=0;i<4;i++)
		{
			InitialBrd N=E;
			if(N.Mvon(i))
				if(Tosolve(dep+1,N)) return true;
		}
	}
	return false;
}

void IDAstar()
{
	InitialBrd E;
	E.GetBrd(sour);
	maxdep=E.heur();
	if(maxdep==0){cout<<"0"<<endl;return;}
	while(!Tosolve(0,E))maxdep+=2;
}

//计算初始状态到目标状太的奇偶性.由判断问题的可解性
bool CanBeSolve()
{
	int *c,count=0,count1=0,i1,j1,i2,j2;
	c= new int[boardsz];

	for(int k =0;k<boardsz;k++)
	{
		c[dest[k]]=sour[k];
		if(sour[k]==0){i1=k/rowsz+1;j1=k%rowsz+1;}
		if(dest[k]==0){i2=k/rowsz+1;j2=k%rowsz+1;}
	}

	int posi =((i1+i2)%2+(j1+j2)%2)%2;
	for(int j=0;j<boardsz;j++)
	{
		int k=c[j],k1=j;
		count1=0;
		while(k>=0){k=c[k1];c[k1]=-1;k1=k;count1++;}
		if(count1>0) count+=count1-2;
	}

	if(count%2==posi)return true;
	else return false;
}

int main()
{

	ifstream fin;

    fin.open("input.txt");  

	fin>>rowsz;
	
	boardsz=rowsz*rowsz;

	sour= new int[boardsz];
	
	dest = new int[boardsz];

	pos = new int[boardsz];

	for(int i=0;i<boardsz;i++)
	{
		fin>>sour[i];
	}
	for(i=0;i<boardsz;i++)
	{
		fin>>dest[i];
		pos[dest[i]]=i;
	}

	if(CanBeSolve())IDAstar();
	else
	{
		ofstream fout;
		fout.open("output.txt");
		fout<<"No Solution!";
		fout.close();
	}

	delete[] sour;
	delete[] dest;
	delete[] pos;

	return 0;
}