c3_maze.cpp

这个是严蔚敏版的数据结构上机教程中的部分源代码

/*
ID:  wangyucao
PROB:MAZE
LAUG:C++
*/
#include <iostream>
#include <fstream>
#include <memory>
#include <queue>
#include <stack>
using namespace std;

struct Node{
	int x,y;
	int step;
//	int sign;
};
Node maze[20][20];
ifstream fin("maze.in");
ofstream fout("maze.out");
int main()
{
	int i,j,row,col,current_step;
	Node start,end,now;
	queue<Node> q;
	stack<Node> s;
//	cout<<"输入行列："<<endl;
	fin>>row>>col;
//	cout<<"输入迷宫(行列顺序，0通，1阻)："<<endl;
	for(i=0;i<row;i++)
		for(j=0;j<col;j++)
		{	fin>>maze[i][j].step;
			maze[i][j].x=i;
			maze[i][j].y=j;
			maze[i][j].step--;
		}
//	cout<<"输入起始行列："<<endl;
	fin>>start.x>>start.y;
	start.x--;start.y--;
//	cout<<"输入结束行列："<<endl;
	fin>>end.x>>end.y;
	end.x--;end.y--;
	start.step=1;
	maze[start.x][start.y].step=start.step;
	q.push(start);

	while(!q.empty())
	{
		now=q.front();
		q.pop();
		if(now.x==end.x && now.y==end.y) break;
		current_step=now.step;
		if(now.x<row-1 && maze[now.x+1][now.y].step<0) 
			{now.x++; 
			 maze[now.x][now.y].step=current_step+1;
			 q.push(maze[now.x][now.y]);
			 now.x--;}
		if(now.y<col-1 && maze[now.x][now.y+1].step<0) 
			{now.y++; 
			maze[now.x][now.y].step=current_step+1; 
			q.push(maze[now.x][now.y]); 
			now.y--;}
		if(now.x>0 && maze[now.x-1][now.y].step<0) 
			{now.x--;  
			maze[now.x][now.y].step=current_step+1;
			q.push(maze[now.x][now.y]);  
			now.x++;}
		if(now.y>0 && maze[now.x][now.y-1].step<0) 
			{now.y--;
			maze[now.x][now.y].step=current_step+1; 
			q.push(maze[now.x][now.y]); 
			now.y++;}
		
	}
	while(!q.empty()) q.pop();
	s.push(end);
	bool flag=false;
	now=end;
	while(!flag)
	{
		if(now.x>0 && maze[now.x-1][now.y].step==maze[now.x][now.y].step-1)
		{
			s.push(maze[now.x-1][now.y]);
			now.x--;			
			if(maze[now.x][now.y].x==start.x && maze[now.x][now.y].y==start.y) {flag=true;}
			continue;
		}
		if(now.y>0 && maze[now.x][now.y-1].step==maze[now.x][now.y].step-1)
		{
			s.push(maze[now.x][now.y-1]);
			now.y--;
			if(maze[now.x][now.y].x==start.x && maze[now.x][now.y].y==start.y) {flag=true;}
			continue;
		}
		if(now.x<row-1 && maze[now.x+1][now.y].step==maze[now.x][now.y].step-1)
		{
			s.push(maze[now.x+1][now.y]);
			now.x++;
			if(maze[now.x][now.y].x==start.x && maze[now.x][now.y].y==start.y) {flag=true;}
			continue;
		}
		if(now.y>col-1 && maze[now.x][now.y+1].step==maze[now.x][now.y].step-1)
		{
			s.push(maze[now.x][now.y+1]);
			now.y++;
			if(maze[now.x][now.y].x==start.x && maze[now.x][now.y].y==start.y) {flag=true;}
			continue;
		}
	}
//	cout<<"迷宫顺序为："<<endl;
	while(s.size()>1)
	{
		now=s.top();
		s.pop();
		fout<<"("<<now.x+1<<','<<now.y+1<<")->";
	}
	now=s.top();
	s.pop();
	fout<<"("<<now.x+1<<','<<now.y+1<<')'<<endl;
	return 0;
}