C語言實現(xiàn)走迷宮

更新時間：2020年07月22日 17:10:08 作者：回城之光

這篇文章主要為大家詳細介紹了C語言實現(xiàn)走迷宮，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了C語言實現(xiàn)走迷宮的具體代碼，供大家參考，具體內(nèi)容如下

描述

給一張個迷宮，問能否從起點走到終點，只能往上下左右走，不能斜著走

輸入

多組測試數(shù)據(jù)，每組第一行兩個正整數(shù)，分別為n和m

表示n這個迷宮有n行m列(0<n,m<10)

接著是n行m列，

'#'表示路

‘*'表示墻

‘S'表示起點

‘T'表示終點

輸出

每組測試數(shù)據(jù)輸出一個結(jié)果，如果能從S走到T，輸出“YES”,否則輸出“NO”

輸入樣例：

2 2
S*
#T
3 3
S*#
#T
##

輸出樣例：

YES
NO

有兩種方法可以解決這個問題

第一種深度優(yōu)先搜索：站在入口，考慮自己下一步可以走哪里，走到下一個位置后，再考慮下一步怎么走，一直走下去，直到?jīng)]有路，然后再返回最近的一個岔路口，選其它任一條沒試過的路，如果不能走，再嘗試其他的路，直到這個岔路口的路全部試完，再回到上一個路口，看是否能走到出口，相當于一條路走到黑

#include<bits/stdc++.h>

using namespace std;
char a[20][20];  //存儲迷宮字符數(shù)組
int flag,m,n;
int sdep_x[4]={-1,1,0,0},sdep_y[4]={0,0,-1,1};//控制上下左右方向
int vis[20][20]; //標記走過的路
void dfs(int x,int y)
{
 vis[x][y]=1; //代表被標記過了
 if(a[x][y]=='T') //找到出口
 {
  flag=1;
  return;
 }
  for(int i=0;i<4;i++) //搜索路徑
  {
   int h=x+sdep_x[i];
   int l=y+sdep_y[i];
   if(a[h][l]!='*'&&!vis[h][l]&&h>=0&&h<n&&l>=0&&l<m)//搜索路徑的條件
   {
    dfs(h,l);
   }
  }
}

int main()
{
 while(cin>>n>>m)
 {
  memset(vis,0,sizeof(vis));//初始化數(shù)組
  flag=0;
  int f,g;
  for(int i=0;i<n;i++)
   for(int j=0;j<m;j++) 
    cin>>a[i][j];
  for(int i=0;i<n;i++)
   for(int j=0;j<m;j++)
   {
    if(a[i][j]=='S')//先找到路口
    {
     f=i;
     g=j;
    }
   }
  dfs(f,g);
  if(flag)
   cout<<"YES"<<endl;
  else
   cout<<"NO"<<endl;
 }
 return 0;
}

第二種方法廣度優(yōu)先搜索：這一步之后，把接下來一步的所有路都列出來，在之后的所有擴展之中，在以一個為下一步，再將所有的該步可以到達的下一步，全部列舉出來，再將第二步的其他選擇中的每一步，都一一做擴展，每次擴展，都要檢查所擴展的地方有沒有到達搜索的要求。
可以定義一個隊列，將擴展的點位置保存在隊列，將擴展完畢的點出隊

#include<bits/stdc++.h>
using namespace std;
int vis[20][20];
char a[20][20];
int n,m;
int step_x[4]={-1,1,0,0},step_y[4]={0,0,-1,1};
struct data//定義一個結(jié)構(gòu)體，里面包含x,y成員                                                         
{
 int x;
 int y;
};
data s,p;//定義兩個結(jié)構(gòu)體變量
queue<data>q;//定義一個隊列q
int BFS()
{
 while(!q.empty())//當隊列不為空時
 {
  p=q.front();//返回隊列的第一個元素
  vis[p.x][p.y]=1;
  q.pop();//刪除隊列中最靠前的元素
  if(a[p.x][p.y]=='T')//如果找到出口
   return 1;
  else
  {
   for(int i=0;i<4;i++)
   {
    s.x=p.x+step_x[i];
    s.y=p.y+step_y[i];
    if(s.x>=0&&s.x<n&&s.y>=0&&s.y<m&&!vis[s.x][s.y]&&a[s.x][s.y]!='*')//搜索條件
     q.push(s);//將擴展的點的位置存入隊尾
   }
  }
 }
 return 0;
}
int main()
{
 while(cin>>n>>m)
 {
  while(!q.empty())
  {
   q.pop();//清空隊列中的元素
  }
  for(int i=0;i<n;i++)
   for(int j=0;j<m;j++)
   cin>>a[i][j];
   for(int i=0;i<n;i++)
   {
   for(int j=0;j<m;j++)
   {
    vis[i][j]=0;
    if(a[i][j]=='S')
    {
     s.x=i;
     s.y=j;
     q.push(s);//將路口的位置保存在隊尾
    }
   }
   }
   if(BFS())
   cout<<"YES"<<endl;
   else
   cout<<"NO"<<endl;

 }
 return 0;
}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: