歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C語言實現迷宮求解

最近做了一個用C語言迷宮求解的題目,來分享一下。

題目要求://迷宮的布局放入到一個二維的數組中 1代表該地方走不通為牆,0代表該地方可以走通,打印出來走的順序
 //0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9
const int mizu[10][10] = {      1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1,  //0
 1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1,  //1
 1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1,  //2
 1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1,  //3
 1 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1,  //4
 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1,  //5
 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1,  //6
  1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1,  //7
  1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1,  //8
  1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1  //9
} ;

分析:

1、可以利用C語言的棧來實現,起點坐標為(1,1),如果該步能走通,把該步的坐標入棧,且對該坐標進行標記,代表已經走過。

2、然後以該坐標(x,y)為中心進行,對該坐標的上(x,y-1)、右(x+1,y)、下(x,y-1)、左(x-1,y)的坐標順時針進行判斷可否走通(可否走通的條件為:該坐標的值為0,同時該步沒有走過),尋找下一步坐標,如果找到了下一步,就接著入棧。

3、如果判斷出來該坐標的四周的四個坐標(上、右、下、左)都不能夠走通,則把該坐標出棧。

4、如果棧不空則接著往下找,如果棧空,則結束,沒有可行的通路。

5、這樣一直進行,找到出口坐標則結束,找到可行的通路


下面是我寫的代碼:有問題大家多交流。

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

//迷宮的布局放入到一個二維的數組中
      //0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9
const int mizu[10][10] = {1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1,  //0
        1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1,  //1
        1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1,  //2
        1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1,  //3
        1 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1,  //4
        1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1,  //5
        1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1,  //6
          1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1,  //7
          1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1,  //8
          1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1  //9
      } ;
int flag[10][10] = {0} ;     
typedef int TypeData ;
typedef struct node{
 TypeData datax ;
 TypeData datay ;
 struct node* next ;
}Node , *LinkList ;

typedef struct stack{
 LinkList top ;
}STACK ;
//************************函數聲明******************************
int stackInit(STACK* s ) ;
int pushStack(STACK* s ,TypeData x , TypeData y) ;
void popStack(STACK* s , TypeData* x , TypeData* y) ;
int isStackEmpty(STACK* s) ;
int mizePath(STACK* s ,TypeData end_x , TypeData end_y ) ;
int passMizu(TypeData x , TypeData y ) ;
//**********************************************************

//鏈棧的初始化
int stackInit(STACK* s )
{
 LinkList p = (LinkList)malloc(sizeof(Node)) ;
 if(!p)  return -1 ;
 p->next = NULL ;
 p->datax = -1 ; 
 p->datay = -1 ;
 s->top = p ;
 return 1 ;
}
//入棧操作
int pushStack(STACK* s ,TypeData x , TypeData y)
{
 LinkList p = (LinkList)malloc(sizeof(Node)) ;
 if(!p)  return -1 ;  //分配內存失敗
 p->datax = x ;
 p->datay = y ;
 p->next = s->top ;
 s->top = p ;
 return 1 ;
}
//出棧的操作
void popStack(STACK* s , TypeData* x , TypeData* y)
{
 LinkList p = s->top ;
 s->top = p->next ;
 (*x) = p->datax ;
 (*y) = p->datay ;
 free(p) ;
}
//判斷棧是否為空
//1 空  0 不空
int isStackEmpty(STACK* s)
{
 if(s->top->datax == -1)  //棧空
  return 1 ;
 return 0 ; 
}
//找到最佳路徑
//end_x , end_y為結束的坐標
//上 、右、下、左尋找方式
int mizePath(STACK* s ,TypeData end_x , TypeData end_y )
{
 pushStack(s , 1 ,1) ; //初始坐標壓棧
 TypeData nowx = 1 , nowy = 1 ;
 flag[nowx][nowy] = 1 ;  //該坐標已經被占用不能再通過
 while(!isStackEmpty(s)) //當棧不空的時候
 {
  if((nowx == end_x)&&(nowy == end_y))
  {
   return 1 ;
  }
//  printf("nowx = %d  nowy = %d\n",nowx , nowy) ;
//  system("PAUSE") ;
  if(passMizu(nowx , nowy-1))  //先向上尋找
  {
   nowy = nowy - 1 ; //坐標更改
   pushStack(s , nowx , nowy) ;  //把該坐標壓棧
   flag[nowy][nowx] = 1 ;  //該坐標已經被占用不能再通過
  }
  else  if(passMizu(nowx+1 , nowy)) //向右尋找 
  {
   nowx = nowx + 1 ;
   pushStack(s , nowx , nowy) ;  //把該坐標壓棧
   flag[nowy][nowx] = 1 ;  //該坐標已經被占用不能再通過
  }
  else if(passMizu(nowx , nowy+1)) //向下尋找
  {
   nowy = nowy + 1 ;
   pushStack(s , nowx , nowy) ;  //把該坐標壓棧
   flag[nowy][nowx] = 1 ;  //該坐標已經被占用不能再通過
  }
  else if(passMizu(nowx-1 , nowy)) //向左尋找
  {
   nowx = nowx - 1 ;
   pushStack(s , nowx , nowy) ;  //把該坐標壓棧
   flag[nowy][nowx] = 1 ;  //該坐標已經被占用不能再通過
  }
  else  //都行不通
  {
   popStack(s , &nowx , &nowy) ;
  }
   
 } //while(!isStackEmpty(s)) //當棧不空的時候
 return 0 ;
}
//判斷該位置是否可通
int passMizu(TypeData x , TypeData y )
{
 if((x > 9)||(y > 9))
  return 0 ;  //越界不可通
 if(mizu[y][x])
  return 0 ;  //該位置是牆,不可通
 if(flag[y][x]) 
  return 0 ;  //該坐標已經被占用,不能通過
 return 1 ;   
}
//打印棧中的數據
int printStackData(STACK s)
{
 STACK temp ;  //新建一個臨時的棧
 stackInit(&temp) ;
 if(s.top->datax == -1)  return 0 ; //棧為空
 while(s.top->datax != -1)
 {
  pushStack(&temp,s.top->datax,s.top->datay);
  s.top = s.top->next ;
 }
 while(temp.top->datax != -1)
 {
  printf("(%d,%d)\n",temp.top->datax , temp.top->datay) ;
  temp.top = temp.top->next ;
 }
 return 1 ;
}
int main()
{
 STACK mi_stack ;
 int i = 0 , j = 0 ;
 stackInit(&mi_stack) ;
 
 if(mizePath(&mi_stack , 8 , 8))
 {
  printStackData(mi_stack) ; //把坐標倒敘打印出來
 } 
 else printf("沒有通路!\n") ;
 
 return  0 ;
}

Copyright © Linux教程網 All Rights Reserved