// 迷宮_遞歸.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream.h>
#include <stack>
struct site{
	int x,y;
	int from,direction;
};
int nx[4],ny[4];
int **maze,**trace;
int out_x,out_y;
bool end=false;
bool find=false;
bool search(int x,int y,int direction)
{
	int new_x,new_y;
	
	if (x==out_x && y==out_y)
	{
		end=true;
		return true;
	}
	else
	{
		find=false;
		for(int i=direction;i<=3;i++)
		{
			if(!find)
			{
				new_x=x+nx[i];
				new_y=y+ny[i];
				if(maze[new_x][new_y]==0 && trace[new_x][new_y]==0)
				{
					find=true;
					trace[new_x][new_y]=1;
					search(new_x,new_y,0);
					if (end)
						cout<<"("<<new_x<<","<<new_y<<")"<<endl;

				}
			}
		}
	}
}


	
int main(int argc, char* argv[])
{


	int m,n;
	int i,j;


	int current_x,current_y,direction;

	

	nx[0]=0 ;
	ny[0]=-1;
	nx[1]=0 ;
	ny[1]=1;
	nx[2]=-1;
	ny[2]=0;
	nx[3]=1;
	ny[3]=0;
	
	cout<<"please input the size of a maze(row,column):";
	cin>>m>>n;
	maze=new int * [m+2];
	trace=new int *[m+2];
	for(i=0;i<=n+1;i++)
	{
		maze[i]=new int[n+2];
		trace[i]=new int[n+2];
	}
	cout<<"Please input the maze data"<<endl;
	for(i=0;i<=n+1;i++)
	{
		maze[0][i]=1;
		maze[m+1][i]=1;
		trace[0][i]=1;
	}	trace[m+1][i]=1;
	for(i=0;i<=m+1;i++)
	{
		maze[i][0]=1;
		maze[i][n+1]=1;
		trace[i][0]=1;
		trace[i][n+1]=1;
	}
	for(i=1;i<=m;i++)
	{
		for (j=1;j<=n;j++)
		{
			cin>>maze[i][j];
			trace[i][j]=0;
		}
	}
    
	
	cout<<"Please input the entry(x,y)";
	cin>>current_x>>current_y;

	while(maze[current_x][current_y]==1)
	{
		cout<<"This site is not exist, please input again!!!"<<endl;
		cin>>current_x>>current_y;
	}
	cout<<"Please input the exit(x,y)";
	cin>>out_x>>out_y;

	trace[current_x][current_y]=1;
	search(current_x,current_y,0);//從入口出發(fā)，開(kāi)始探測(cè)。按照東西北南的順序，現(xiàn)探測(cè)東向
	
	if (end)
	{
		cout<<"("<<current_x<<","<<current_y<<")"<<endl;
		cout<<"\nThere is a path"<<endl;
	}
	else
		cout<<"\nThere is not a path"<<endl;


}