maze.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include <fstream>

using namespace std;
class maze
{
public:
	maze(ifstream &);
	~maze();
	bool search();
private:
	struct Node
	{
		long f;
		long x,y;
	};
	ofstream out;
	void sort(Node *);
	bool backtrack(long,long,long,long);
	long m;
	bool **grid;
	long p,q;
	long r,s;
};

maze::maze(ifstream & in)   //输入
{
	long k,i,x,y;
	in>>m>>k;
	grid=new bool*[m];
	for(i=0;i<m;i++)
		grid[i]=new bool[m];
	for(long j=0;j<m;j++)
		for(i=0;i<m;i++)
			grid[j][i]=true;       //最初为true
	for(i=0;i<k;i++)
	{
		in>>x>>y;
		grid[x-1][y-1]=false;     //封闭为false 
	}
	in>>p>>q>>r>>s; 
	out.open("output.txt");
}
maze::~maze()
{
	long i;
	for(i=0;i<m;i++)
		delete[] grid[i];
	delete[] grid;
}
bool maze::search()
{
	return backtrack(p,q,0,0);
}
bool maze::backtrack(long x,long y,long x1,long y1)   
{
	if(x==r&&y==s)          //遇到终点，打印坐标
	{
		out<<r<<" "<<s<<endl;
		return true;          //返回true,表示已经找到终点
	}
	Node *node;
	node=new Node[4];         //4个方向的坐标及到终点的距离
	if(x>1&&x-1!=x1)         //如果不是(x,y)的前面格子(x1,y1)，防止走回头路，且不越界
	{
		node[0].x =x-1;    //node[0]   上
		node[0].y =y;
		node[0].f =abs(r-x+1)+abs(s-y);    //距离终点两坐标相减取绝对值 
	}
	else
	{
		node[0].x=node[0].y=0;     //如果是(x,y)的前面格子(x1,y1)，或者越界，将坐标写为(0,0)
		node[0].f= 0x7fffffff;     //消耗改为有符号整数最大
	}
	if(y<m&&y+1!=y1)              //以下三个相同
	{
		node[1].x =x;    //node[1]   右
		node[1].y =y+1;
		node[1].f =abs(r-x)+abs(s-y-1);
	}
	else
	{
		node[1].x=node[1].y=0;
		node[1].f= 0x7fffffff;
	}
	if(x<m&&x+1!=x1)
	{
		node[2].x =x+1;    //node[2]   下
		node[2].y =y;
		node[2].f =abs(r-x-1)+abs(s-y);
	}
	else
	{
		node[2].x=node[2].y=0;
		node[2].f= 0x7fffffff;
	}
	if(y>1&&y-1!=y1)
	{
		node[3].x =x;    //node[3]   左
		node[3].y =y-1;
		node[3].f =abs(r-x)+abs(s-y+1);
	}
	else
	{
		node[3].x=node[3].y=0;
		node[3].f= 0x7fffffff;
	}
	sort(node);       //进行排序，从小到大 ，找到最短路经   
	if(node[0].x&&node[0].f!=0x7fffffff )    //   不为0（看上面）
		if(grid[node[0].x-1][node[0].y-1])    // 不是封闭的
			if(backtrack(node[0].x,node[0].y,x,y))    //递归寻找
			{                                       //如果找到，即递归下去遇到if(x==r&&y==s)为真，返回
				out<<x<<" "<<y<<endl;           //输出当前坐标
				return true;                     //逐级返回true
			}
	if(node[1].x&&node[1].f!=0x7fffffff )                            //上面的路不通，下一个。。。。。。。
		if(grid[node[1].x-1][node[1].y-1])
			if(backtrack(node[1].x,node[1].y,x,y))
			{
				out<<x<<" "<<y<<endl;
				return true;
			}
	if(node[2].x&&node[2].f!=0x7fffffff )
		if(grid[node[2].x-1][node[2].y-1])
			if(backtrack(node[2].x,node[2].y,x,y))
			{
				out<<x<<" "<<y<<endl;
				return true;
			}
	if(node[3].x&&node[3].f!=0x7fffffff )
		if(grid[node[3].x-1][node[3].y-1])
			if(backtrack(node[3].x,node[3].y,x,y))
			{
				out<<x<<" "<<y<<endl;
				return true;
			}
	return false; //如果四个方向都没有结果，返回false找不到
}
void maze::sort(maze::Node * node)
{
	Node temp;
	for(long i=0;i<3;i++)
		for(long j=i+1;j<4;j++)
			if(node[i].f>node[j].f)
			{
				temp=node[i];
				node[i]=node[j];
				node[j]=temp;
			}
}
void main()
{
	ifstream in("input.txt");
	maze m(in);
	if(!m.search())
	{
		ofstream out("output.txt");
		out<<"No Solution!"<<endl;
	}
}