migong.cpp

自己编写的迷宫

#include <iostream.h>
const int m=6,n=8;
int mark[m+2][n+2];
int move[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{1,-1}};
int maze[m+2][n+2]={
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,0,0,0,0,0,0,1},
	{1,1,0,0,1,1,1,1,0,1},
	{1,0,0,0,0,0,0,0,0,1},
	{1,1,1,0,1,1,1,1,1,1},
	{1,0,0,0,0,0,1,0,1,1},
	{1,1,0,1,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1}};
int w=0,l=0;
int a[n*m][2],c[n*m][2];

int seekpath(int x,int y )
{
	int i,g,h;
	if((x==m)&&(y==n))   
		return 1;
	for(i=0;i<8;i++)
	{
		g=x+move[i][0];
		h=y+move[i][1];
		if((maze[g][h]==0)&&(mark[g][h]==0))
		{
			mark[g][h]=-1;
			if(seekpath(g,h))
			{
				a[l][0]=g;
				a[l][1]=h;
				l++;
				cout<<"("<<g<<","<<h<<")，";
				return 1;
			}
		}
	}
	if((x==1)&&(y==1))
		cout<<"No path!"<<endl;
	return 0;
}



int seekpath2(int x,int y )
{                            
	int i,g,h,j;	             
	  if((x==m)&&(y==n))   
		return 1;
	for(i=0;i<8;i++)
	{
		g=x+move[i][0];
		h=y+move[i][1];
		if((maze[g][h]==0)&&(mark[g][h]!=-2))
		{
			mark[g][h]=-2;
			if(seekpath2(g,h))
			{
				a[l][0]=g;
				a[l][1]=h;
				l++;
				return 1;
			}
		}
	}
	if((x==c[w][0])&&(y==c[w][1]))
		return 0;
	return 0;
}




void main( )
{
	int i,j,h,y,x;
	for(i=0;i<m+2;i++)
	{
		cout<<endl;
			for(j=0;j<n+2;j++)
				cout<<maze[i][j]<<" ";
	}
	cout<<endl;
		//初始化数组
		for(i=0;i<m+2;i++)
			for(j=0;j<n+2;j++)
				mark[i][j]=0;
			mark[1][1]=-1;
			cout<<"其中一条路径为："<<endl;
			if(seekpath(1,1))
			{
				a[l][0]=1;
				a[l][1]=1;
				cout<<"(1,1)"<<endl;
				for(i=0;i<=l;i++)
					for(j=0;j<2;j++)
					c[i][j]=a[i][j];		
				for(w=l;w>=0;w-- )
				{
					h=w;
					if(c[h][0]==-100||c[h][1]==-100)
						break;
					i=w-1;
					j=c[i][1];
					i=c[i][0];            
                    mark[i][j]=-2;
                    h=l;
					l=0;
					if (seekpath2(c[w][0],c[w][1]))
					{
						l--;
						j=w-1;
						if(l<h)
						{                    
							for( ;l>=0;l--,j--)
								for(i=0;i<2;i++)
								c[j][i]=a[l][i];
							for( ;j>=0;j--)
								for(i=0;i<2;i++)
									c[j][i]=-100;
						}
					}
				}
				cout<<"最短路径为："<<endl;
                for(i=0; ;i++)
				{
					if(c[i][0]==0||c[i][1]==0)
						break;
					if(c[i][0]!=-100||c[i][1]!=-100)
					cout<<"("<<c[i][0]<<","<<c[i][1]<<"),";
				    
				}
			}
			cout<<endl;
             
}