SOGO論壇

標題: c++程式問題 [列印本頁]

作者: gabrielle 時間: 2010-11-8 11:10:58 標題: c++程式問題

有高手能幫我解釋這個程式嗎?

#include <stdio.h>
#include <stdlib.h>
#define EAST  MAZE[x][y+1]  /*定義東方的相對位置*/
#define WEST  MAZE[x][y-1]  /*定義西方的相對位置*/
#define SOUTH MAZE[x+1][y]       /*定義南方的相對位置*/
#define NORTH MAZE[x-1][y]       /*定義北方的相對位置*/
#define ExitX 8             /*定義出口的X座標在第八列*/
#define ExitY 10             /*定義出口的Y座標在第十行*/
struct list
{
      int x,y;
      struct list* next;
};
typedef struct list node;
typedef node* link;
int MAZE[10][12] = {1,1,1,1,1,1,1,1,1,1,1,1,       /*宣告迷宮陣列*/
               1,0,0,0,1,1,1,1,1,1,1,1,
               1,1,1,0,1,1,0,0,0,0,1,1,
               1,1,1,0,1,1,0,1,1,0,1,1,
               1,1,1,0,0,0,0,1,1,0,1,1,
               1,1,1,0,1,1,0,1,1,0,1,1,
               1,1,1,0,1,1,0,1,1,0,1,1,
               1,1,1,1,1,1,0,1,1,0,1,1,
               1,1,0,0,0,0,0,0,1,0,0,1,
               1,1,1,1,1,1,1,1,1,1,1,1};
link push(link stack,int x,int y);
link pop(link stack,int* x,int* y);
int chkExit();
int main()
{
      int i,j,x,y;
      link path = NULL;
      x=1;       /*入口的X座標*/
      y=1; /*入口的Y座標*/
      printf("[迷宮的路徑(0的部分)]\n"); /*印出迷宮的路徑圖*/
      for(i=0;i<10;i++)
      {
            for(j=0;j<12;j++)
                     printf("%2d",MAZE[j]);
            printf("\n");
      }
while(x<=ExitX&&y<=ExitY)
      {
            MAZE[x][y]=2;
            if(NORTH==0)
            {
                     x -= 1;
                     path=push(path,x,y);
            }
            else if(SOUTH==0)
            {
                     x+=1;
                     path=push(path,x,y);
            }
            else if(WEST==0)
            {
                     y-=1;
                     path=push(path,x,y);
            }
            else if(EAST==0)
            {
                     y+=1;
                     path=push(path,x,y);
            }
            else if(chkExit(x,y,ExitX,ExitY)==1) /*檢查是否走到出口了*/
                     break;
            else
            {
                     MAZE[x][y]=2;
                     path=pop(path,&x,&y);
            }
      }
printf("[老鼠走過的路徑(2的部分)]\n"); /*印出老鼠走完迷宮後的路徑圖*/
      for(i=0;i<10;i++)
      {
            for(j=0;j<12;j++)
                     printf("%2d",MAZE[j]);
            printf("\n");
      }
      system("pause");
      return 0;
}
link push(link stack,int x,int y)
{
      link newnode;
      newnode = (link)malloc(sizeof(node));
      if(!newnode)
      {
            printf("Error!記憶體配置失敗!\n");
            return NULL;
      }
      newnode->x=x;
      newnode->y=y;
      newnode->next=stack;
      stack=newnode;
return stack;
}
link pop(link stack,int* x,int* y)
{
      link top;
      if(stack!=NULL)
      {
            top=stack;
            stack=stack->next;
            *x=top->x;
            *y=top->y;
            free(top);
            return stack;
      }
      else
            *x=-1;
      return stack;
}

作者: alphi 時間: 2010-11-8 19:30:40

這在資料結構中,應該是最基礎的題目.只是一般常用都是使用遞迴處理.

這個程式則是不用遞迴,在加上使用Linked-List 連結串列去紀錄老鼠走過得路徑.如果改用遞迴程式碼不超過20行吧

作者: chiasa 時間: 2010-11-11 00:14:15

觀念就是走下一步時，要先把目前這步的位置記下來 (push)
如果前面沒路了，就退回上一步(pop)，改走另一個方向

歡迎光臨 SOGO論壇 (https://oursogo.com/)