lab_1_1.cpp.bak

利用优化算法

#include<iostream>
using namespace std;

const m=12,n=15;
int maze[m+2][n+2]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
                    {1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
                    {1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
                    {1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
                    {1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},
                    {1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},
                    {1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
                    {1,0,0,1,1,0,1,1,1,0,1,0,0,1,1,1,1},
                    {1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1},
                    {1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
                    {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1},
                    {1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
                    {1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
                    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
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}};

struct PathNode
{
	int row,colum,diretion;
	}Path[m*n];


	

int SeekPath(int x,int y,int l)
{
    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(l=SeekPath(g,h,l))
    	{
    		Path[l].row=x;Path[l].colum=y;Path[l].diretion=i;
    		l++;
			maze[x][y]=8;
    		return l;
    		}
    	}
	}
	if((x==1)&&(y==1))
	    cout<<"No path!"<<endl;
	return 0;
}
void main()
{
	int i,j,l;
	
	for(i=0;i<m+2;i++)
	    for(j=0;j<n+2;j++)
	        mark[i][j]=0;
	mark[1][1]=1;
	
	if(l=SeekPath(1,1,0))
	{	
	    for(l=l-1;l>0;l--)	
	    	cout<<"("<<Path[l].row<<","<<Path[l].colum<<","<<Path[l].diretion<<")"<<endl;
	    for(i=1;i<m+1;i++)
		{
			for(j=1;j<n+1;j++)
				cout<<maze[i][j]<<" ";
			cout<<"\n";
		}
	}
}