迷宮問題

[cpp]
//功能：利用遞歸調用完成迷宮問題的求解  
#include <stdio.h>  
#include <stdlib.h>  
#include <conio.h>  
#include <time.h>  
//申明迷宮函數  
int maze(char **a,int m,int n); 
 
//定義全局變量i,j用來存放迷宮數組的行數和列數  
int i,j; 
 
int main() 
{ 
    int k; 
    int m,n; 
    char **a;//定義指向迷宮數組的二維指針  
    printf("\n************************************迷宮問題************************************"); 
    printf("\t\t1、輸入自己的迷宮\n\t\t2、系統隨機產生一個迷宮\n"); 
    scanf("%d",&k); 
    printf("輸入迷宮的行數和列數:"); 
    scanf("%d%d",&i,&j); 
    getchar(); 
    //動態分配迷宮數組的存儲區域  
    a=(char **)malloc(sizeof(char *)*i); 
    for(m=0;m<i;m++) 
    { 
        a[m]=(char *)malloc(sizeof(char)*j); 
    } 
    //輸入自己的迷宮數組元素  
    if(k==1) 
    { 
        printf("輸入一個迷宮數組，用1表示牆壁，用0表示空白區域\n"); 
        for(m=0;m<i;m++) 
        { 
            for(n=0;n<j;n++) 
            { 
                a[m][n]=getchar(); 
            } 
            getchar(); 
        } 
        printf("你輸入的迷宮為：\n"); 
        for(m=0;m<i;m++) 
        { 
            for(n=0;n<j;n++) 
            { 
                printf(" %c ",a[m][n]); 
            } 
            printf("\n"); 
        } 
    } 
    //系統初始化一個迷宮數組  
    else 
    { 
        //初始化一個迷宮數組並隨機產生牆壁與空白，用1表示牆壁，用0表示空白區域  
        srand((int)time(0)); 
        for(m=0;m<i;m++) 
        { 
            for(n=0;n<j;n++) 
            { 
                a[m][n]=rand()%2+'0'; 
                printf(" %c ",a[m][n]); 
            } 
            printf("\n"); 
        } 
    } 
    if(maze(a,0,0)) 
    { 
        printf("找到了路徑！\n"); 
        for(m=0;m<i;m++) 
        { 
            for(n=0;n<j;n++) 
            { 
                printf(" %c ",a[m][n]); 
            } 
            printf("\n"); 
        } 
    } 
    else 
    { 
        printf("該迷宮為死迷宮！\n"); 
    } 
    getch(); 
    return 0; 
} 
 
int maze(char **a,int m,int n) 
{ 
    int k; 
    //該條件用於首次判斷  
    if(a[m][n]=='1') 
        return 0; 
    a[m][n]='2'; 
    if(m==i-1 && n==j-1 && a[m][n]=='2') 
        return 1;    
    //向下走  
    if(m+1<i && a[m+1][n]=='0') 
    { 
        k=maze(a,m+1,n); 
        if(k==1) 
            return 1; 
    } 
    //向上走  
    if(m-1>-1 && a[m-1][n]=='0') 
    { 
        k=maze(a,m-1,n); 
        if(k==1) 
            return 1; 
    }    
    //向右走  
    if(n+1<j && a[m][n+1]=='0') 
    { 
        k=maze(a,m,n+1); 
        if(k==1) 
            return 1; 
    } 
    //向左走  
    if(n-1>-1 && a[m][n-1]=='0') 
    { 
        k=maze(a,m,n-1); 
        if(k==1) 
            return 1; 
    } 
    a[m][n]='0'; 
    return 0; 
} 

//功能：利用遞歸調用完成迷宮問題的求解
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
//申明迷宮函數
int maze(char **a,int m,int n);

//定義全局變量i,j用來存放迷宮數組的行數和列數
int i,j;

int main()
{
 int k;
 int m,n;
 char **a;//定義指向迷宮數組的二維指針
 printf("\n************************************迷宮問題************************************");
 printf("\t\t1、輸入自己的迷宮\n\t\t2、系統隨機產生一個迷宮\n");
 scanf("%d",&k);
 printf("輸入迷宮的行數和列數:");
 scanf("%d%d",&i,&j);
 getchar();
 //動態分配迷宮數組的存儲區域
 a=(char **)malloc(sizeof(char *)*i);
 for(m=0;m<i;m++)
 {
  a[m]=(char *)malloc(sizeof(char)*j);
 }
 //輸入自己的迷宮數組元素
 if(k==1)
 {
  printf("輸入一個迷宮數組，用1表示牆壁，用0表示空白區域\n");
  for(m=0;m<i;m++)
  {
   for(n=0;n<j;n++)
   {
    a[m][n]=getchar();
   }
   getchar();
  }
  printf("你輸入的迷宮為：\n");
  for(m=0;m<i;m++)
  {
   for(n=0;n<j;n++)
   {
    printf(" %c ",a[m][n]);
   }
   printf("\n");
  }
 }
 //系統初始化一個迷宮數組
 else
 {
  //初始化一個迷宮數組並隨機產生牆壁與空白，用1表示牆壁，用0表示空白區域
  srand((int)time(0));
  for(m=0;m<i;m++)
  {
   for(n=0;n<j;n++)
   {
    a[m][n]=rand()%2+'0';
    printf(" %c ",a[m][n]);
   }
   printf("\n");
  }
 }
 if(maze(a,0,0))
 {
  printf("找到了路徑！\n");
  for(m=0;m<i;m++)
  {
   for(n=0;n<j;n++)
   {
    printf(" %c ",a[m][n]);
   }
   printf("\n");
  }
 }
 else
 {
  printf("該迷宮為死迷宮！\n");
 }
 getch();
 return 0;
}

int maze(char **a,int m,int n)
{
 int k;
 //該條件用於首次判斷
 if(a[m][n]=='1')
  return 0;
 a[m][n]='2';
 if(m==i-1 && n==j-1 && a[m][n]=='2')
  return 1; 
 //向下走
 if(m+1<i && a[m+1][n]=='0')
 {
  k=maze(a,m+1,n);
  if(k==1)
   return 1;
 }
 //向上走
 if(m-1>-1 && a[m-1][n]=='0')
 {
  k=maze(a,m-1,n);
  if(k==1)
   return 1;
 } 
 //向右走
 if(n+1<j && a[m][n+1]=='0')
 {
  k=maze(a,m,n+1);
  if(k==1)
   return 1;
 }
 //向左走
 if(n-1>-1 && a[m][n-1]=='0')
 {
  k=maze(a,m,n-1);
  if(k==1)
   return 1;
 }
 a[m][n]='0';
 return 0;
}