migong.cpp

回溯法求迷宫问题

#include <iostream>
using namespace std;
#include <fstream>
#include "make2db.h"

class pointer
{
public:
	int x,y;
};

void main()
{
	int k,n,N,*dire;
	int **maze,**mark;
	pointer *path;
	pointer move[5];
	ifstream fin("data.txt");
	if(!fin)
	{
		cout<<"文件data.txt不能被打开"<<endl;
		exit(1);
	}
	fin>>n;
	Make2DArray(maze,n,n);
	Make2DArray(mark,n,n);
	N=(n-2)*(n-2);
	path=new pointer[N];
	dire=new int[N];
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			fin>>maze[i][j];
			mark[i][j]=1;
		}
	}
	for(i=1;i<5;i++)
	{
		fin>>move[i].x>>move[i].y;
	}
	fin.close();
	for(i=0;i<N;i++)
	{
		dire[i]=0;
	}

	k=1;
	path[0].x=1;
	path[0].y=1;
	mark[1][1]=0;
	while(k>0)
	{
		if(dire[k]<4)
		{
			dire[k]++;
			path[k].x=path[k-1].x+move[dire[k]].x;
			path[k].y=path[k-1].y+move[dire[k]].y;
			if(maze[path[k].x][path[k].y]&&mark[path[k].x][path[k].y])
			{
				mark[path[k].x][path[k].y]=0;
				if(path[k].x==(n-2)&&path[k].y==(n-2))
				{
					cout<<"("<<path[0].x<<","<<path[0].y<<")";
					for(int i=1;i<=k;i++)
					{
						cout<<"->("<<path[i].x<<","<<path[i].y<<")";
					}
					cout<<endl<<endl;
				}
				else
					k=k+1;
			}
		}
		else
		{
			dire[k]=0;
			k=k-1;
		}
	}
	remove2DArray(maze,n);
	remove2DArray(mark,n);
	delete [] path;
	delete [] dire;
}