migong.cpp

绝对没有毒的文件 请放心下载 绝对绝对能狗彻底的运行 请放心

// migong.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stack>
#include <iostream>
using namespace std;

struct site
{
	int x,y;
	int direct;
};
int main(int argc, char* argv[])
{
	stack<site> site_stack;

	int m,n;
	int **maze;
	int i,j;
	int ** trace;

	int current_x,current_y,out_x,out_y,direction,from;

	int nx[4],ny[4];

	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;

	site start;
	start.x=current_x;
	start.y=current_y;
	start.direct=-1;
	site_stack.push(start);
	

	while(!site_stack.empty() && !(current_x==out_x &&current_y==out_y))
	{
		site temp;
		int x,y;
		int direction;

		temp=site_stack.top();
		x=temp.x;
		y=temp.y;
		direction=temp.direct+1;
		
		x=x+nx[direction];
		y=y+ny[direction];//探测方向

		//site_stack.top().direct +=1;//在当前位置的下一个探测方向

		while((maze[x][y]==1 ||trace[x][y]==1)&& direction<=3)
		{
			temp=site_stack.top();
			
		
			x=temp.x+nx[direction];
			y=temp.y+ny[direction];
			site_stack.top().direct=direction;
			direction+=1;
		}
		if (maze[x][y]==0&&trace[x][y]==0)
		{
			trace[x][y]=1;
			temp.x=x;
			temp.y=y;
			temp.direct=0;
			site_stack.push(temp);
			current_x=x;
			current_y=y;
		}
		else
			site_stack.pop();
	}


	site path;
	
	while(!site_stack.empty () )
	{
		path=site_stack.top();
		cout<<"("<<path.x <<","<<path.y<<")"<<"  ";
		site_stack.pop ();

	}
	
	return 0;
}