動態迷宮建立與探測顯示 (C語言)

//===============================================================
// 20090522/28 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1509060202905 (討人厭的-匿名)
// http://tw.knowledge.yahoo.com/question/question?qid=1009060111697
// 發問者 :(Sonic ) http://tw.knowledge.yahoo.com/my/my?show=AC02165077
//===============================================================

又是迷宮題...只是發問者之一是令人討人厭的匿名, 所以程式當然就不照需求來寫...不過有符合純C.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//                     空地  起點  終點  路徑  牆壁
const  char *sym[] = { "　", "→", "→", "◇", "█" };
const int SPACE = 0;
const int START = 1;
const int END = 2;
const int PATH = 3;   //  路徑
const int WALL = 4;   //  牆壁

char *maze;
int m_Col, m_Row;
int m_Start, m_End;
int m_Size;

//顯示迷宮
void ShowMaze()
{
  int i;
  for(i=0; i<m_Size; )
  {
     printf( "%s", sym[maze[i]]);
     if(++i%m_Col==0) printf("\n");
  }
  printf("\n");
}
//路徑尋找: 回傳由[b]到[e]的路徑數量
int Visit(int b, int e, int s)
{ // s=1 有路徑時顯示
  int n=1;
  if (maze[b]!=SPACE) return 0;
  maze[b] = PATH;    //設定為走過的地方
  if (b!=e)
    n = Visit(b+1,e,s)+ Visit(b+m_Col,e,s)+ Visit(b-1,e,s) + Visit(b-m_Col,e,s);
  else if (s) ShowMaze(); //有路徑 n=1;
  maze[b] = SPACE;
  return n;
}

int dir[4] = { 1, 2, -1, -2 };  // 方向探測
// 更新方向探測的 向下 與 向上 值
void UpdateDir()
{
  dir[1] = m_Col;  dir[3] = -m_Col;
}
// 探測迷宮
int Traverse(int b, int l, int d )
{  // b:進入點;  l:=0右側,=1左側;  d:進入的方向; 
   int n, nx, i;
   i=(maze[b]==END);
   maze[b] = PATH;
   ShowMaze();
   if (i) return 1;
   i=(l)? 3: 1;
   for( n=0, d=(d+i)%4; n<4; n++, d=(d+i+2)%4 )
   {
     nx = b+dir[d];
     if (maze[nx]==WALL) continue;
     if (maze[nx]!=PATH && Traverse( nx, l, d)) return 1;
     ShowMaze();
   }
   maze[b] = SPACE;
   return 0;
}
// 建立迷宮
int CreateMaze(int row, int col)
{
  int r, c, p, m, n, i;
  m_Row = (row<4)? 4: row;
  m_Col = (col<4)? 4: col;
  m_Size = m_Row*m_Col;
  maze = (char *) malloc(sizeof(char)*m_Size); // 配置記憶體
  if (maze==NULL) return 0;
  for(i=0; i<m_Size; i++) maze[i] = WALL;
  m_Start = (rand()%(m_Row-2)+1)*m_Col;  // 若起點為左上角改 = m_Col;
  m_End = (rand()%(m_Row-2)+2)*m_Col-1;  // 若終點為右下角改 = m_Col*(m_Row-1) - 1
  maze[m_Start++]=START;  maze[m_Start]=SPACE;
  maze[m_End--]=END;  maze[m_End]=SPACE;

  p = (m_Col-2)*(m_Row-2);
  while(Visit(m_Start, m_End, 0 )!=1 || p>0 )
  {
    r = rand()%(m_Row-2)+1;
    c = rand()%(m_Col-2)+1;
    i = r*m_Col+c;
    if (maze[i]==SPACE) continue;  // 已經是空地了
    maze[i]=SPACE;
    m = Visit(i, m_Start, 0);  //連接起點路徑數量
    if (m<2)
    {
      n = Visit(i, m_End, 0 );   //連接終點路徑數量
      p = (m==1 && n==1)? (m_Col-2)*(m_Row-2): p-1;
      if ((m==1 && n<2) || (n==1 && m<2) ) continue;
    }else p--;
    maze[i]=WALL;
  }
  UpdateDir();
  return 1;
}
// === 主程式 ===
int main()
{
  int r, c;
  char w='A';
  srand((unsigned)time(NULL));
  while(w!='0')
  {
    printf("\n 請輸入迷宮大小(行Column與列Row兩個數目,負值離開):");
    if (scanf("%d", &c)!=1 || c<0 || scanf("%d", &r)!=1 || r<0) break;
    if (!CreateMaze(r,c)) break;   // 設定迷宮大小 (失敗離開)
    printf("\n顯示迷宮[%dx%d] :\n", m_Col, m_Row );
    ShowMaze();
    printf("\n\n顯示路徑 :\n");
    Visit(m_Start, m_End, 1 );
    fflush(stdin);
    printf("\n 是否要顯示探測路徑? 0)離開 1)右側探測 2)左側探測  其它)繼續下個迷宮 :");
    scanf( "%c", &w);
    if (w=='1') Traverse(m_Start, 0, 0);  // 右側探測
    else if (w=='2') Traverse(m_Start, 1, 0);  // 左側探測
    free(maze);  // 釋放記憶體
  }
  return 0;
}
//====