迷宫问题

// exam1.cpp : 定义控制台应用程序的入口点。

//

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

int maze[10][10]={
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1}
};

typedef struct
{
	pair<int,int> pos;
	int dir;
}SElem;

bool pass(int maze[][10], SElem cur,SElem& nstep)
{
	switch(cur.dir)
	{
		case 1:
			nstep.pos.first=cur.pos.first;
			nstep.pos.second=cur.pos.second+1;
			break;
		case 2:
			nstep.pos.first=cur.pos.first+1;
			nstep.pos.second=cur.pos.second;
			break;
		case 3:
			nstep.pos.first=cur.pos.first;
			nstep.pos.second=cur.pos.second-1;
			break;
		case 4:
			nstep.pos.first=cur.pos.first-1;
			nstep.pos.second=cur.pos.second;
			break;
		default:
			return false;
	}
	if(maze[nstep.pos.first][nstep.pos.second]==0)
	{
		nstep.dir=1;
		return true;
	}
	else
	{
		return false;
	}
}

bool next_step(int maze[][10],stack<SElem> &path,SElem& nstep)
{
	SElem cur;
	while(!path.empty())
	{
		cur=path.top();
		if(pass(maze,cur,nstep))
		{
			//path.push(nstep);
			return true;
		}
		else
		{
			while(!path.empty() && cur.dir==4)
			{
				path.pop();
				cur=path.top();
			}
			if(!path.empty())
			{
				path.top().dir++;
			}
			else
			{
				return false;
			}
		}
	}
	
	return false;	
}

void maze_path(int maze[][10], stack<SElem> &path, SElem& end)
{
	SElem nstep;
	do
	{
		if(next_step(maze,path,nstep))
		{
			path.push(nstep);

			maze[nstep.pos.first][nstep.pos.second]=2;

			if(end.pos.first==nstep.pos.first && end.pos.second==nstep.pos.second)
			{
				break;
			}
		}
		else
		{
			break;
		}
	}while(1);
}

void show_path(int maze[][10], stack<SElem>& path)
{
	SElem cur;
	while(!path.empty())
	{
		cur=path.top();
		maze[cur.pos.first][cur.pos.second]=3;
		path.pop();
	}

	cout<<"The maze path is:"<<endl;
	for(int i=0;i<10;i++)
	{
		for(int j=0;j<10;j++)
		{
			int tmp=maze[i][j];
			if(tmp==1)
			{
				cout<<"##";
			}
			else if(tmp==3)
			{
				cout<<"- ";
			}
			else
			{
				cout<<"  ";
			}
		}
		cout<<endl;
	}

	return;
}

int main(void)
{
	stack<SElem> path;
	SElem start,end;
	start.pos=make_pair<int,int>(1,1);
	start.dir=1;
	path.push(start);
	end.pos=make_pair<int,int>(8,8);

	maze_path(maze,path,end);

	show_path(maze,path);

	system("pause");
	return 0;
}