puzzle.cpp

AI作业合集

//#include<iostream.h>
#include<stdio.h>
#include<stdlib.h> //标准库
#define n1 10 
#define n2 10 
typedef struct node 
{ 
int intX; //存intX坐标
int intY; //存intY坐标
int intDirection;  //存该点可能的下点所在的方向,1表示向右,2向上,3向左,4向右
}linkstack; 

linkstack stackTop[100]; 
//迷宫矩阵
int maze[n1][n2]={1,1,1,1,1,1,1,1,1,1, 
    0,0,0,1,0,0,0,1,0,1, 
    1,1,0,1,0,0,0,1,0,1, 
    1,0,0,0,0,1,1,0,0,1, 
    1,0,1,1,1,0,0,0,0,1, 
    1,0,0,0,1,0,0,0,0,0, 
    1,0,1,0,0,0,1,0,0,1, 
    1,0,1,1,1,0,1,1,0,1, 
    1,1,0,0,0,0,0,0,0,1, 
    1,1,1,1,1,1,1,1,1,1,}; 

int i,j,k,m=0;

main() 
{
//初始化stackTop[],置所有方向数为左
for(i=0;i<n1*n2;i++) 
{
stackTop[i].intDirection=1;
}

cout<<"The Maze is:"<<endl;


//打印原始迷宫矩阵 
for(i=0;i<n1;i++) 
{ 
 for(j=0;j<n2;j++) 
 printf(maze[i][j]?"* ":"  "); 
// cout<<maze[i][j]?"* ":"  "<<endl;
 printf("\n"); 
} 
i=0;stackTop[i].intX=1;stackTop[i].intY=0;
maze[1][0]=2;
/*回溯算法*/
do
{
 if(stackTop[i].intDirection<5)    //还可以向前试探
 {
  if(stackTop[i].intX==5 && stackTop[i].intY==9) //已找到一个组合
  {
   //打印路径
   printf("The way %d is:\n",m++);
   for(j=0;j<=i;j++) 
   {
    printf("(%d,%d)-->",stackTop[j].intX,stackTop[j].intY);
   }
   printf("\n");

   //打印选出路径的迷宫
   for(j=0;j<n1;j++) 
   { 
    for(k=0;k<n2;k++) 
    {
     if(maze[j][k]==0) printf("  ");
     else if(maze[j][k]==2)  printf("O ");
     else printf("* ");
    }
    printf("\n"); 
   } 

   maze[stackTop[i].intX][stackTop[i].intY]=0;
   stackTop[i].intDirection = 1;
   i--;
   stackTop[i].intDirection += 1;
   continue;
  }
  switch (stackTop[i].intDirection)   //向前试探
  {
   case 1:
    {
     if(maze[stackTop[i].intX][stackTop[i].intY+1]==0)
     {
      i++;
      stackTop[i].intX=stackTop[i-1].intX;
      stackTop[i].intY=stackTop[i-1].intY+1;
      maze[stackTop[i].intX][stackTop[i].intY]=2;
     }
     else
     {
      stackTop[i].intDirection += 1;
     }
     break;
    }
   case 2:
    {
     if(maze[stackTop[i].intX-1][stackTop[i].intY]==0)
     {
      i++;
      stackTop[i].intX=stackTop[i-1].intX-1;
      stackTop[i].intY=stackTop[i-1].intY;
      maze[stackTop[i].intX][stackTop[i].intY]=2;
     }
     else
     {
      stackTop[i].intDirection += 1;
     }
     break;
    }
   case 3:
    {
     if(maze[stackTop[i].intX][stackTop[i].intY-1]==0)
     {
      i++;
      stackTop[i].intX=stackTop[i-1].intX;
      stackTop[i].intY=stackTop[i-1].intY-1;
      maze[stackTop[i].intX][stackTop[i].intY]=2;
     }
     else
     {
      stackTop[i].intDirection += 1;
     }
     break;
    }
   case 4:
    {
     if(maze[stackTop[i].intX+1][stackTop[i].intY]==0)
     {
      i++;
      stackTop[i].intX=stackTop[i-1].intX+1;
      stackTop[i].intY=stackTop[i-1].intY;
      maze[stackTop[i].intX][stackTop[i].intY]=2;
     }
     else
     {
      stackTop[i].intDirection += 1;
     }
     break;
    }
  }
 }
 else   //回溯
 {
  if(i==0) return 0;   //已找完所有解
  maze[stackTop[i].intX][stackTop[i].intY]=0;
  stackTop[i].intDirection = 1;
  i--;
  stackTop[i].intDirection += 1;
 }
}while(1);
}