溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

C語(yǔ)言如何實(shí)現(xiàn)走迷宮

發(fā)布時(shí)間：2020-07-22 10:10:27 來(lái)源：億速云 閱讀：126 作者：小豬 欄目：開(kāi)發(fā)技術(shù)

小編這次要給大家分享的是C語(yǔ)言如何實(shí)現(xiàn)走迷宮，文章內(nèi)容豐富，感興趣的小伙伴可以來(lái)了解一下，希望大家閱讀完這篇文章之后能夠有所收獲。

描述

給一張個(gè)迷宮，問(wèn)能否從起點(diǎn)走到終點(diǎn)，只能往上下左右走，不能斜著走

輸入

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

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

接著是n行m列，

'#'表示路

‘*'表示墻

‘S'表示起點(diǎn)

‘T'表示終點(diǎn)

輸出

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

輸入樣例：

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

輸出樣例：

YES
NO

有兩種方法可以解決這個(gè)問(wèn)題

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

#include<bits/stdc++.h>

using namespace std;
char a[20][20];   //存儲(chǔ)迷宮字符數(shù)組
int flag,m,n;
int sdep_x[4]={-1,1,0,0},sdep_y[4]={0,0,-1,1};//控制上下左右方向
int vis[20][20];  //標(biāo)記走過(guò)的路
void dfs(int x,int y)
{
  vis[x][y]=1;  //代表被標(biāo)記過(guò)了
  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)先搜索：這一步之后，把接下來(lái)一步的所有路都列出來(lái)，在之后的所有擴(kuò)展之中，在以一個(gè)為下一步，再將所有的該步可以到達(dá)的下一步，全部列舉出來(lái)，再將第二步的其他選擇中的每一步，都一一做擴(kuò)展，每次擴(kuò)展，都要檢查所擴(kuò)展的地方有沒(méi)有到達(dá)搜索的要求。
可以定義一個(gè)隊(duì)列，將擴(kuò)展的點(diǎn)位置保存在隊(duì)列，將擴(kuò)展完畢的點(diǎn)出隊(duì)

#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//定義一個(gè)結(jié)構(gòu)體，里面包含x,y成員                                                                                                                 
{
  int x;
  int y;
};
data s,p;//定義兩個(gè)結(jié)構(gòu)體變量
queue<data>q;//定義一個(gè)隊(duì)列q
int BFS()
{
  while(!q.empty())//當(dāng)隊(duì)列不為空時(shí)
  {
    p=q.front();//返回隊(duì)列的第一個(gè)元素
    vis[p.x][p.y]=1;
    q.pop();//刪除隊(duì)列中最靠前的元素
    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);//將擴(kuò)展的點(diǎn)的位置存入隊(duì)尾
      }
    }
  }
  return 0;
}
int main()
{
  while(cin>>n>>m)
  {
    while(!q.empty())
    {
      q.pop();//清空隊(duì)列中的元素
    }
    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);//將路口的位置保存在隊(duì)尾
        }
      }
     }
     if(BFS())
      cout<<"YES"<<endl;
     else
      cout<<"NO"<<endl;

  }
  return 0;
}

看完這篇關(guān)于C語(yǔ)言如何實(shí)現(xiàn)走迷宮的文章，如果覺(jué)得文章內(nèi)容寫(xiě)得不錯(cuò)的話，可以把它分享出去給更多人看到。

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手