動態迷宮建立 (C語言)

//===============================================================
// 20090522/28 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1509052205422
// http://tw.knowledge.yahoo.com/question/question?qid=1609052807673
// 發問者 :(wsx01 ) http://tw.knowledge.yahoo.com/my/my?show=AC04892662
//===============================================================

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

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

//顯示迷宮
void ShowMaze()
{             //  空地  路徑  牆壁
  char *sym[] = { "　", "◇", "█" };
  for(int i=0; i<m_Size; )
  {
     printf( "%s", sym[maze[i]]);
     if(++i%m_Col==0) printf("\n");
  }
}
//路徑尋找: 回傳由[b]到[e]的路徑數量
int Visit(int b, int e, int s)
{ // s!=0 有路徑時顯示
  int n=1;
  if (maze[b]!=0) return 0;
  maze[b] = 1;    //設定為走過的地方
  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] = 0;
  return n;
}
// 建立迷宮
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] = 2;
  maze[ m_Start=m_Col+1 ] = 0;
  maze[ m_End=m_Col*(m_Row-1)-2 ] = 0;

  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]==0) continue;  // 已經是空地了
     maze[i]=0;
    m = Visit(i, m_Start, 0);  //連接起點路徑數量
     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;
    maze[i]=2;
  }
  return 1;
}
// === 主程式 ===
int main()
{
  int r, c;
  srand((unsigned)time(NULL));
  while(1)
  {
    printf("\n 請輸入迷宮大小(行Column與列Row兩個數目,負值離開):");
    if (scanf("%d", &c)!=1 || c<0 || scanf("%d", &r)!=1 || r<0) break;
    if (!CreateMaze(r,c)) break;   // 設定迷宮大小 (失敗離開)
    Visit(m_Start, m_End, 1 );
    free(maze);  // 釋放記憶體
  }
  system("pause");
  return 0;
}
//====