老鼠走迷宮程序實例  
 

 


/*--------------------------------------------------------------------------------------------
//文件名稱：MazeMouse.cpp
//功    能：找出走出迷宮的所有路徑，以及最短路徑。

#include "stdafx.h"
#include "iostream.h"
#include "string.h"
#include "stdio.h"

double dMeans=0,dWalkLen=10000;//dMeans表示走出迷宮的方法，dWalkLen表示當前走出迷宮最少步數             
char Maze[10][52]={
     {"###################################################"},
     {"% ## ####           ###                  ### # ####"},
     {"# ##  # ###  ### ###### ### ############ #   #    #"},
     {"# ## ## ###  ##  ##     # # ## #           #   ####"},
     {"# #    # ## ##  ### #          # ######### # # # ##"},
     {"#      # #   # ##     ########## ####   ##   #    #"},
     {"# ## ### ## ## ### #### ##    ##    # # ######### #"},
     {"# #  #      ## ##       #  ##  #### # #  ##    ####"},
     {"####   ## ####    ####    ##  # ###   ##    ##    @"},
     {"###################################################"},
    };            //迷宮
int MazeFlag[10][51];  //迷宮的標志：0表示未走過，i(i=1,2,3,4)表示已經走過了,i表示方向。
int MazeMin[10][51];   //路徑最小的迷宮的標志

void Walk(int nx,int ny);//走迷宮的函數，nx是列，ny是行
void PrintOut();         //打印路徑及迷宮的函數，同時比較獲取路徑較短的行走方法
int  Judge(int nx,int ny,int i);//判斷在第nx列ny行向第i個方向走是否可以,可以返回1否則返回0。
                                //i=1表示向右，2表示向下，3表示向左，4表示向上

/*---------------------------------------------------------------------------------------------
//行走迷宮函數： void Walk (int nx,int ny)
//功能：判斷是否已經走出迷宮，如果走出則打印路徑，如果沒有則開始逐個方向判斷是否可以行走，
//      如果都不能行走，或已經返回。則退出該位置，即將該位置的標志寫為0表明未走過。
//無返回值，形參nx為當前位置的列，ny為當前位置的行。
---------------------------------------------------------------------------------------------*/
void Walk(int nx,int ny)
{
 if (Maze[nx][ny]=='@')//判斷是否走出迷宮，@是迷宮出口標志
  PrintOut();       //走出則打印出迷宮及行走路徑
 else                  //未走出迷宮
 {
  for (int i=1; i<=4; i++)//四個方向逐個行走，i=1向右 2向下 3向左 4向上
  {
   if (Judge(nx,ny,i)) //如果列為nx行為ny的位置向i方向是否可以行走
   {                   
    MazeFlag[nx][ny]=i;//將標志位置i表明該位置向i方向可行走

    if (i==1)          //分散處理，根據不同的i來確定下一步的位置，以便行走。
     Walk(nx,ny+1);
    else if (i==2)
     Walk(nx+1,ny);
    else if (i==3)
     Walk(nx,ny-1);
    else if (i==4)
     Walk(nx-1,ny);
   }
  }
  
  MazeFlag[nx][ny]=0;//如果4個方向都走不通，或者回朔則清空該點標志位，置為0表明未走過。
 }

}


/*---------------------------------------------------------------------------------------------
//打印函數：void PrintOut()
//功能：    打印第dMeans種方法的在迷宮中的行走路徑,以及通過比較找出目前行走步數最少的行走方法。
//無返回值，無形參。dMeans表示當前行走方法的種類。dCount是用來計算此種方法用了多少步。
---------------------------------------------------------------------------------------------*/
void PrintOut()
{
 int nx,ny;
 double dCount=0;

 dMeans++;

 cout<<"The "<<dMeans<<" ways is: "<<endl;
 
 for (nx=0;nx<10;nx++)
 {
  for (ny=0;ny<51;ny++)
  {
   if (Maze[nx][ny]=='#')//＃表示墻
    cout<<"#";
   else if (MazeFlag[nx][ny]==0)//不是墻但未走過的地方用空格表示
    cout<<" ";
   else                 //不是墻且走過的地方用*表示
   {
    cout<<".";
    dCount++;       //走一步總步數加1
   }
  }
  cout<<endl;
 }

 cout<<"This way used "<<dCount<<" steps"<<endl;

 if (dCount<dWalkLen)//如果此種方法的步數比以前方法中最少步數還要少，
 {                   //則將此種方法列為當前最少行走步數
  for (nx=0;nx<10;nx++)
   for(ny=0;ny<51;ny++)
    MazeMin[nx][ny]=MazeFlag[nx][ny];
  dWalkLen=dCount;
 }
}


/*--------------------------------------------------------------------------------------------
//判斷函數：int Judge(int nx,int ny,int i)
//功能：    判斷當前位置(nx為列ny為行)向第i方向行走是否可以
//返回值int型 返回1表明可以，0表示不可以
--------------------------------------------------------------------------------------------*/
int Judge(int nx,int ny,int i)
{
 if (i==1)//判斷向右可否行走
 {
  if (ny<50&&(Maze[nx][ny+1]==' '||Maze[nx][ny+1]=='@')&&MazeFlag[nx][ny+1]==0)
   return 1;
  else
   return 0;
 }
 else if (i==2)//判斷向下可否行走
 {
  if (nx<9&&(Maze[nx+1][ny]==' '||Maze[nx+1][ny]=='@')&&MazeFlag[nx+1][ny]==0)
   return 1;
  else 
   return 0;
 }
 else if (i==3)//判斷向左可否行走
 {
  if (ny>0&&(Maze[nx][ny-1]==' '||Maze[nx][ny-1]=='@')&&MazeFlag[nx][ny-1]==0)
   return 1;
  else
   return 0;
 }
 else if (i==4)//判斷向上可否行走
 {
  if (nx>0&&(Maze[nx-1][ny]==' '||Maze[nx-1][ny]=='@')&&MazeFlag[nx-1][ny]==0)
   return 1;
  else
   return 0;
 }
 else
  return 0;

}

 

int main(int argc, char* argv[])
{
 int nx,ny,ni,nj;

 cout<<"迷宮游戲: "<<endl;
 
 for (ni=0;ni<10;ni++)//輸出迷宮形狀，并且找到迷宮的入口，同時將迷宮標志初始化
 { 
  for(nj=0;nj<51;nj++)
  {
   cout<<Maze[ni][nj];
   MazeFlag[ni][nj]=0;//將迷宮標志初始化為0表示未走過
   if (Maze[ni][nj]=='%')
   {
    nx=ni;//迷宮入口列坐標
    ny=nj;//迷宮入口行坐標
   }
  }
  cout<<endl;
 }
 
 cout<<endl<<"入口坐標:"<<endl<<"nx= "<<nx<<"   "<<"ny= "<<ny<<endl; 

 Walk(nx,ny);//調用行走迷宮函數，從入口處開始行走

 cout<<endl<<"The MinLen way is: "<<endl;

 for (nx=0;nx<10;nx++)//輸出最短路徑
 {
  for (ny=0;ny<51;ny++)
  {
   if (Maze[nx][ny]=='#')
    cout<<"#";
   else if (MazeMin[nx][ny]==0)
    cout<<" ";
   else
   {
    cout<<".";
   }
  }
  cout<<endl;
 }

 cout<<"This Way used "<<dWalkLen<<" steps"<<endl;//輸出最短路徑總行走步數

 return 0;
}