老鼠走迷宮

wc_big_pig天尊

這是小弟最近利用點空檔寫的，一共有三個版本，由淺而深，從第二個版本開始，包含動態配置與鏈結的觀念。與大家一同分享此作。由於小弟註解已經寫的夠清楚了，所以就不再針對程式碼做贅述。

第一版：
record.h

//用此類別來紀錄走訪過的路，含有堆疊的特性
#ifndef RECORD_H
#define RECORD_H
class RECORD_ROAD
{
      private:
              int row,col;
      public:
             void pop(int* r,int* c){*r = row; *c = col;}
             void push(int r,int c){row = r;col = c;}
};
#endif

mouse.cpp

/*題目：老鼠走迷宮陣列版本 ,以該迷宮一定有路徑可以達到終點為前提
1.使用物件陣列來儲存走訪的路徑，記憶體使用上有些許浪費
2.走訪的方法，則是使用巢狀if else結構來完成
*/
#include <cstdlib>
#include <iostream>
#include "record.h"//RECORD_ROAD類別與實做的宣告
#include <windows.h>//COORD結構的宣告
using namespace std;


const int row_size = 14;//迷宮圖列
const int col_size = 17;//迷宮圖行
int top = 0;

void draw_map(bool map[row_size][col_size]);//畫出迷宮圖
void gotoxy(int x,int y);//設置列印座標
void print_path(RECORD_ROAD* record_road);//列印出路徑

     
int main(int argc, char *argv[])
{
//將迷宮的外層圍一層牆壁
bool map[row_size][col_size] = {{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,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,0,1,1},
                                {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,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,1,1,1},
                                {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1,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 row = 1,col = 1;//起點(1,1)
   RECORD_ROAD record_road[100];//利用物件陣列來紀錄走過的座標
  
   
   draw_map(map);//畫出迷宮圖案  
   record_road[top].push(row,col);//push (1,1)
   map[row][col] = 1;//凡走過，則將該圖上的位置標示為 1  
   
   //當座標還沒有到達終點之前，繼續走訪
   while((row != row_size-2)||(col != col_size-2))
   {
              if(map[row-1][col] == 0 )//正上方
              {
                   row--;            
              }
              else if(map[row-1][col+1]==0 )//右上方
              {
                   row--;   col++;
              }
              else if(map[row][col+1]==0 )//右方
              {
                   col++;
              }
              else if(map[row+1][col+1]==0 )//右下方
              {
                   row++;    col++;                  
              }
              else if(map[row+1][col]==0)//下方
              {
                   row++;                  
              }
              else if(map[row+1][col-1]==0 )//左下方
              {
                   row++;    col--;
              }
              else if(map[row][col-1]==0 )//左方
              {
                   col--;
              }
              else if(map[row-1][col-1]==0 )//左上方
              {
                   row--;    col--;
              }
              else//當目前的座標位置沒有路可以前進時
              {   
                  top--;
                  //返回前一步的座標   
                  
                  record_road[top].pop(&row,&col);
                  //pop前一步的座標
                  
                  continue;
                  //重新判斷是否有方向可以走訪      
              }  
               //如果有路可以走的話，則前進並且紀錄目前的座標
               
               top++;
               //前進
               
               record_road[top].push(row,col);
               //將目前的座標紀錄下來
               
               map[row][col] = 1;
               //凡走過，則將該圖上的位置標示為 1
   }
    print_path(record_road);
    //將物件陣列的位址pass給function
                  
    system("PAUSE");
    return EXIT_SUCCESS;
}

void draw_map(bool map[row_size][col_size])
{   
    int row,col;
    for(row=0; row<row_size; row++)
    {
               for(col=0; col<col_size; col++)
               {         
                    if(row==0||row==13)cout<<"-";
               else if(col==0||col==16)cout<<"|";
               else
                   cout<< (map[row][col]== 1? "x":"o");
               }
               cout<<endl;
    }  
}
void gotoxy(int x,int y)//設置列印座標
{
    COORD c;
    c.X = x;
    c.Y = y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c);
    //設置終端機滑鼠指標位置
}

void print_path( RECORD_ROAD* record_road)
{
     int row,col;
     //列印出可以走到終點的路徑
   for(int i=0; i<=top; i++)
   {      
           record_road.pop(&row,&col);//將走訪過路徑pop出來
           
           gotoxy(col,row);//col行，代表是x座標；row列，代表是y座標
           
           cout<<static_cast<char>(1);
           _sleep(200);//is included in stdlib.h參數為毫秒 200->0.2秒
   }        
}

第二版：
record.h

//用此類別來紀錄走訪過的路，含有堆疊的特性
#ifndef RECORD_H
#define RECORD_H
class RECORD_ROAD
{
      private:
              int row,col;
      public:
             void pop(int* r,int* c){*r = row; *c = col;}
             void push(int r,int c){row = r;col = c;}
             RECORD_ROAD* forward,*next;//雙向鏈結
};
#endif

mouse2.cpp

/*題目：老鼠走迷宮鏈結串列版,以該迷宮一定有路徑可以達到終點為前提
1.使用雙向鏈結串列來儲存走訪的路徑，可達到節省記憶體的效果
2.走訪的方法，則是使用巢狀if else結構來完成
*/
#include <cstdlib>
#include <iostream>
#include "record.h"//RECORD_ROAD類別與實做的宣告
#include <windows.h>//COORD結構的宣告
using namespace std;


const int row_size = 14;//迷宮圖列
const int col_size = 17;//迷宮圖行

void draw_map(bool map[row_size][col_size]);//畫出迷宮圖
void gotoxy(int x,int y);//設置列印座標
void print_path(RECORD_ROAD* first_point);//列印出路徑


     
int main(int argc, char *argv[])
{
//將迷宮的外層圍一層牆壁
bool map[row_size][col_size] = {{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,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,0,1,1},
                                {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,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,1,1,1},
                                {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1,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 row = 1,col = 1;//起點(1,1)
   RECORD_ROAD *first_point,*this_point;
   
   draw_map(map);//畫出迷宮圖案  
   this_point = first_point = new RECORD_ROAD;//建立第一個節點
   this_point->push(row,col);//push (1,1)
   map[row][col] = 1;//凡走過，則將該圖上的位置標示為 1  
   
   //當座標還沒有到達終點之前，繼續走訪
   while((row != row_size-2)||(col != col_size-2))
   {
              if(map[row-1][col] == 0 )//正上方
              {
                   row--;            
              }
              else if(map[row-1][col+1]==0 )//右上方
              {
                   row--;   col++;
              }
              else if(map[row][col+1]==0 )//右方
              {
                   col++;
              }
              else if(map[row+1][col+1]==0 )//右下方
              {
                   row++;    col++;                  
              }
              else if(map[row+1][col]==0)//下方
              {
                   row++;                  
              }
              else if(map[row+1][col-1]==0 )//左下方
              {
                   row++;    col--;
              }
              else if(map[row][col-1]==0 )//左方
              {
                   col--;
              }
              else if(map[row-1][col-1]==0 )//左上方
              {
                   row--;    col--;
              }
              else//當目前的座標位置沒有路可以前進時
              {   
                  this_point = this_point->forward;
                  //退回前一步
                  
                  delete(this_point->next);
                  //釋放原位置記憶體
                  
                  this_point->pop(&row,&col);
                  //pop出前一個位置的座標
                  
                  continue;
                  //重新判斷是否有方向可以走訪      
              }  
           //如果有路可以走的話，則前進並且紀錄目前的座標
           
               this_point->next = new RECORD_ROAD;
           //動態配置一個新的節點並且指定給this_point->next這個指標
           
               this_point->next->forward = this_point;
            //將現在的位置指定給下一個節點中的forward指標   
               
               this_point = this_point->next;
               //位置往前移一格
               
               this_point->push(row,col);
               //將目前座標紀錄下來
               
               map[row][col] = 1;
               //凡走過，則將該圖上的位置標示為 1
   }
    print_path(first_point);
    //將首節點位址pass給function
                       
    system("PAUSE");
    return EXIT_SUCCESS;
}

void draw_map(bool map[row_size][col_size])
{   
    int row,col;
    for(row=0; row<row_size; row++)
    {
               for(col=0; col<col_size; col++)
               {         
                    if(row==0||row==13)cout<<"-";
               else if(col==0||col==16)cout<<"|";
               else
                   cout<< (map[row][col]== 1? "x":"o");
               }
               cout<<endl;
    }  
}
void gotoxy(int x,int y)//設置列印座標
{
    COORD c;
    c.X = x;
    c.Y = y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c);
    //設置終端機滑鼠指標位置
}

void print_path(RECORD_ROAD* first_point)//列印出路徑
{
     int row,col;
     RECORD_ROAD* this_point;
     //列印出可以走到終點的路徑
     
      this_point=first_point;
     //從第一個節點開始
     
      while(this_point!=NULL)
      {  //當節點不存在時候就跳出  
   
           this_point->pop(&row,&col);//將走訪過路徑pop出來
           
           gotoxy(col,row);//col行，代表是x座標；row列，代表是y座標
           
           cout<<static_cast<char>(1);
           _sleep(300);//is included in stdlib.h參數為毫秒 300->0.3秒
           
           this_point = this_point->next;
           //靠著next來移動節點
      }  
}

第三版：
record.h

//用此類別來紀錄走訪過的路，含有堆疊的特性
#ifndef RECORD_H
#define RECORD_H
class RECORD_ROAD
{
      private:
              int row,col;
      public:
             void pop(int* r,int* c){*r = row; *c = col;}
             void push(int r,int c){row = r;col = c;}
             RECORD_ROAD* forward,*next;//雙向鏈結
};
#endif

direction.h

#ifndef DIRECTION_H
#define DIRECTION_H
//利用列舉型態名稱來作為陣列的索引值，將索引值帶入則可以得到方向值
enum DIR{top, r_top, right, r_down, down, l_down, left, l_top};
short r_value[8] = {-1,-1,0,1,1, 1, 0,-1};
short c_value[8] = { 0, 1,1,1,0,-1,-1,-1};
#endif

mouse3.cpp

/*題目：老鼠走迷宮鏈結串列版，以該迷宮一定有路徑可以達到終點為前提
1.使用雙向鏈結串列來儲存走訪的路徑，可達到節省記憶體的效果
2.使用enum來建立方向表，利用方向表來走訪(請見direction.h)
*/
#include <cstdlib>
#include <iostream>
#include "record.h"//RECORD_ROAD類別與實做的宣告
#include "direction.h"
#include <windows.h>//COORD結構的宣告
using namespace std;


const int row_size = 14;//迷宮圖列
const int col_size = 17;//迷宮圖行

void draw_map(bool map[row_size][col_size]);//畫出迷宮圖
void gotoxy(int x,int y);//設置列印座標
void print_path(RECORD_ROAD* first_point);//列印出路徑


     
int main(int argc, char *argv[])
{
//將迷宮的外層圍一層牆壁
bool map[row_size][col_size] = {{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,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,0,1,1},
                                {1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,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,1,1,1},
                                {1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1,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}};
   bool go_ahead;
   int row = 1,col = 1;//起點(1,1)
   RECORD_ROAD *first_point,*this_point;
   
   
   draw_map(map);//畫出迷宮圖案  
   this_point = first_point = new RECORD_ROAD;//建立第一個節點
   this_point->push(row,col);//push (1,1)
   map[row][col] = 1;//凡走過，則將該圖上的位置標示為 1  
   
   //當座標還沒有到達終點之前，繼續走訪
   while((row != row_size-2)||(col != col_size-2))
   {
         go_ahead = false;
         
        // 判斷八個方向中是否有可以前進的路，由top開始，順時鐘找尋
         for(int dir = top; dir<=l_top; dir++)
         {
                 //有路可以前進的時候
              if(map[row+r_value[dir]][col+c_value[dir]] == 0 )
              {
                   row += r_value[dir];
                   col += c_value[dir];
                   go_ahead = true;
                   //標記可以前進，以便辨認要執行pop或是push
                    
                   break;//找到可以前進的路，就跳出迴圈
              }
         }
         //如果go_ahead沒有被標記為true代表目前的位置沒有路可以前進
         //所以要執行pop動作
         if(! go_ahead)
         {
              this_point = this_point->forward;
              //退回前一步
                  
              delete(this_point->next);
              //釋放原位置記憶體
                  
              this_point->pop(&row,&col);
              //pop出前一個位置的座標
                  
              continue;
              //重新判斷是否有方向可以走訪
         }      
         //反之，代表有路可以走，則前進，執行push的動作
         else
         {
             this_point->next = new RECORD_ROAD;
             //動態配置一個新的節點並且指定給this_point->next這個指標
           
             this_point->next->forward = this_point;
             //將現在的位置指定給下一個節點中的forward指標   
               
             this_point = this_point->next;
             //位置往前移一格
               
             this_point->push(row,col);
             //將目前座標紀錄下來
               
             map[row][col] = 1;
             //凡走過，則將該圖上的位置標示為 1
           }
   }
    print_path(first_point);
    //將首節點位址pass給function
                       
    system("PAUSE");
    return EXIT_SUCCESS;
}

void draw_map(bool map[row_size][col_size])
{   
    int row,col;
    for(row=0; row<row_size; row++)
    {
               for(col=0; col<col_size; col++)
               {         
                    if(row==0||row==13)cout<<"-";
               else if(col==0||col==16)cout<<"|";
               else
                   cout<< (map[row][col]== 1? "x":"o");
               }
               cout<<endl;
    }  
}
void gotoxy(int x,int y)//設置列印座標
{
    COORD c;
    c.X = x;
    c.Y = y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c);
    //設置終端機滑鼠指標位置
}

void print_path(RECORD_ROAD* first_point)//列印出路徑
{
     int row,col;
     RECORD_ROAD* this_point;
     //列印出可以走到終點的路徑
     
      this_point=first_point;
     //從第一個節點開始
     
      while(this_point!=NULL)
      {  //當節點不存在時候就跳出  
   
           this_point->pop(&row,&col);//將走訪過路徑pop出來
           
           gotoxy(col,row);//col行，代表是x座標；row列，代表是y座標
           
           cout<<static_cast<char>(1);
           _sleep(300);//is included in stdlib.h參數為毫秒 300->0.3秒
           
           this_point = this_point->next;
           //靠著next來移動節點
      }  
}