migong.cpp

常用算法与数据结构原代码

#include <iostream.h>
#define m 5
#define n 5
#define MAXN 400

typedef struct node{
	int x,y,pre;
} NODE;

int mg[m+2][n+2];

NODE s[MAXN];

int en_queue(NODE s[],int &h,int &t,NODE x)
{
	t=(t+1) % MAXN;
	if (h==t)
	{
		t=(t+MAXN-1) % MAXN;
		return 1;
	}
	s[t]=x;
	return 0;
}

int de_queue(NODE s[],int &h,int &t,NODE &x)
{
	if (h==t)
		return 1;
	h=(h+1) % MAXN;
	x=s[h];
	return 0;
}

void print(int rear)
{
	int i=rear;
	do{
		cout<<s[i].x<<"  "<<s[i].y<<endl;
		i=s[i].pre;
	}
	while (i!=0);
}

void solve()
{
	int i,j,x,y,v,find,rear,front;
	NODE sel;
	int zx[]={1,0,-1,0},zy[]={0,1,0,-1};
	rear=front=0;
    find=0;
	sel.x=sel.y=1;
	sel.pre=0;
	en_queue(s,front,rear,sel);
	mg[1][1]=-1;
	while (front!=rear && !find)
	{
		de_queue(s,front,rear,sel);
		x=sel.x; y=sel.y;
		for (v=0;v<4;v++)
		{
			i=x+zx[v];
			j=y+zy[v];
			if (mg[i][j]==0)
			{
				sel.x=i;
				sel.y=j;
				sel.pre=front;
				en_queue(s,front,rear,sel);
				mg[i][j]=-1;
			}
			if (i==m && j==n)
			{
				print(rear);
				find=1;
			}
		}
	}
	if (!find)
		cout<<"Not find!"<<endl;
}

void main()
{
	int i,j;
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
			cin>>mg[i][j];
	for (i=0;i<=m+1;i++)
		mg[i][0]=mg[i][n+1]=1;
	for (j=0;j<=n+1;j++)
		mg[0][j]=mg[m+1][j]=1;
	solve();
}