03.c

算法设计与分析实验报告

#include<stdio.h>
#include<graphics.h>
#include<conio.h>

struct coordinate
{  int x;
   int y;
   int sign;
};

struct stack
{  int x;
   int y;
};  /*定义堆栈*/

struct coordinate XY[17][17];
struct stack stack[100];
int n=16,k=0,r=0;

int signq[16][16]={
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{0,0,0,0,0,1,0,1,1,0,1,0,1,0,0,1},
	{1,1,1,1,0,1,0,1,0,0,0,0,0,0,1,1},
	{1,0,0,0,0,1,0,0,0,1,1,0,1,1,1,1},
	{1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1},
	{1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
	{1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1},
	{1,0,0,1,0,0,0,0,0,0,1,0,1,0,0,1},
	{1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1},
	{1,1,1,0,1,0,1,0,0,0,0,0,0,0,0,1},
        {1,1,0,0,0,0,1,1,0,1,0,1,1,0,1,1},
        {1,0,0,1,1,1,1,1,0,1,1,0,0,0,0,1},
        {1,1,0,0,0,0,0,0,0,0,1,0,1,1,1,1},
        {1,1,1,0,1,1,1,1,0,1,1,0,0,0,0,1},
        {1,0,0,0,1,1,0,0,0,1,1,0,1,1,0,0},
        {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
};  /*初始化迷宫*/

void cover(int i,int j)
{
   setfillstyle(1,6);
   rectangle(XY[i][j].x,XY[i][j].y,XY[i+1][j+1].x,XY[i+1][j+1].y);
   floodfill((XY[i][j].x+XY[i+1][j+1].x)/2,(XY[i][j].y+XY[i+1][j+1].y)/2,15);

} /*覆盖走过的路径*/

void move(int i,int j,int h)
{
     setfillstyle(1,4);
     circle((XY[i][j].x+XY[i+1][j+1].x)/2,(XY[i][j].y+XY[i+1][j+1].y)/2,h/4);
     floodfill((XY[i][j].x+XY[i+1][j+1].x)/2,(XY[i][j].y+XY[i+1][j+1].y)/2,15);
} /*移动棋子*/

void block(int i,int j)
{
  line(XY[i][j].x,XY[i][j].y,XY[i+1][j+1].x,XY[i+1][j+1].y);
  line(XY[i][j+1].x,XY[i][j+1].y,XY[i+1][j].x,XY[i+1][j].y);
}  /*标记走过的路径，画×*/

int draw(int a,int b)
{  int i,j;
   int h,l=300;
       h=l/n;
   for(i=0;i<17;i++)
     for(j=0;j<17;j++)
      { XY[i][j].x=a+j*h;
        XY[i][j].y=b+i*h;
      }
   for(i=0;i<17;i++)
    {
      line(XY[0][i].x,XY[0][i].y,XY[n][i].x,XY[n][i].y);
      line(XY[i][0].x,XY[i][0].y,XY[i][n].x,XY[i][n].y);
    }
   for(i=0;i<16;i++)
     for(j=0;j<16;j++)
      {
	if(signq[i][j]==0)
	{
	   setfillstyle(1,6);
	   rectangle(XY[i][j].x,XY[i][j].y,XY[i+1][j+1].x,XY[i+1][j+1].y);
           floodfill((XY[i][j].x+XY[i+1][j+1].x)/2,(XY[i][j].y+XY[i+1][j+1].y)/2,15);
	}
	if(signq[i][j]==1)
	{
	    setfillstyle(1,1);
	    rectangle(XY[i][j].x,XY[i][j].y,XY[i+1][j+1].x,XY[i+1][j+1].y);
            floodfill((XY[i][j].x+XY[i+1][j+1].x)/2,(XY[i][j].y+XY[i+1][j+1].y)/2,15);
	}
      }
	  move(1,0,h);
     return h;
}  /*画大图*/

void find(int a,int b,int h)
{  int a1=a,b1=b;

    if(a==14&&b==15)
    { settextstyle(3,HORIZ_DIR,5);
      setcolor(4);
      outtextxy(415,160,"successful!");
     getch();
     return;
    } /*标记出口*/  

   if(XY[a][b].sign==2)
    { if(signq[a+1][b]==0&&XY[a+1][b].sign<XY[a1][b1].sign) 
        {a1=a+1;
         b1=b;
        } 
       if(signq[a][b+1]==0&&XY[a][b+1].sign<XY[a1][b1].sign) 
        {a1=a;
         b1=b+1;
        } 
       if(signq[a-1][b]==0&&XY[a-1][b].sign<XY[a1][b1].sign) 
        {a1=a-1;
         b1=b;
        } 
       getch();
       move(a1,b1,h);
       cover(a,b);
       signq[a][b]=1;
       XY[a1][b1].sign=1;
       stack[k].x=b;
       stack[k].y=a;
         k++;       
       getch();
       find(a1,b1,h);   
    }

   if(XY[a][b].sign==0||XY[a][b].sign==1) 
     { if(signq[a+1][b]==0&&XY[a+1][b].sign<XY[a1][b1].sign) 
        {a1=a+1;
         b1=b;
        } 
       if(signq[a][b+1]==0&&XY[a][b+1].sign<XY[a1][b1].sign) 
        {a1=a;
         b1=b+1;
        } 
       if(signq[a-1][b]==0&&XY[a-1][b].sign<XY[a1][b1].sign) 
        {a1=a-1;
         b1=b;
        } 
       if(signq[a][b-1]==0&&XY[a][b-1].sign<XY[a1][b1].sign) 
        {a1=a;
         b1=b-1;
        }            
       if(a1==a&&b1==b)
        {a1=stack[k-1].y;
         b1=stack[k-1].x;
           k--; 
         getch();            
         move(a1,b1,h);
         cover(a,b);
         block(a,b);
         signq[a][b]=1;          
         getch();
         find(a1,b1,h);      
        }
      else 
        { stack[k].x=b;
          stack[k].y=a;
            k++;       
          getch();           
          move(a1,b1,h);
          cover(a,b);
          XY[a1][b1].sign=1;
          getch();
          find(a1,b1,h);
        }
      }
}  /*走迷宫*/

void main()
{int graphdriver=DETECT,graphmode;
 int h,i,j;
 initgraph(&graphdriver,&graphmode,"");
  cleardevice();
  for(i=0;i<17;i++)
     {
      for(j=0;j<17;j++)
      {
       XY[i][j].sign=0;
      }
     } 
  XY[1][0].sign=2;       
  h=draw(100,40);
  getch();
  find(1,0,h);
  getch();
  closegraph();
}