C语言如何实现走迷宫-创新互联

创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商，新人活动买多久送多久，划算不套路！

成都创新互联主打移动网站、网站设计、成都网站设计、网站改版、网络推广、网站维护、域名与空间、等互联网信息服务，为各行业提供服务。在技术实力的保障下，我们为客户承诺稳定，放心的服务，根据网站的内容与功能再决定采用什么样的设计。最后，要实现符合网站需求的内容、功能与设计，我们还会规划稳定安全的技术方案做保障。

小编这次要给大家分享的是C语言如何实现走迷宫，文章内容丰富，感兴趣的小伙伴可以来了解一下，希望大家阅读完这篇文章之后能够有所收获。

描述

给一张个迷宫，问能否从起点走到终点，只能往上下左右走，不能斜着走

输入

多组测试数据，每组第一行两个正整数，分别为n和m

表示n这个迷宫有n行m列(0<n,m<10)

接着是n行m列，

'#'表示路

‘*'表示墙

‘S'表示起点

‘T'表示终点

输出

每组测试数据输出一个结果，如果能从S走到T，输出“YES”,否则输出“NO”

输入样例：

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

输出样例：

YES
NO

有两种方法可以解决这个问题

第一种深度优先搜索：站在入口，考虑自己下一步可以走哪里，走到下一个位置后，再考虑下一步怎么走，一直走下去，直到没有路，然后再返回最近的一个岔路口，选其它任一条没试过的路，如果不能走，再尝试其他的路，直到这个岔路口的路全部试完，再回到上一个路口，看是否能走到出口，相当于一条路走到黑

#include<bits/stdc++.h>

using namespace std;
char a[20][20];   //存储迷宫字符数组
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));//初始化数组
    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;
}

当前标题：C语言如何实现走迷宫-创新互联
当前地址：https://www.cdcxhl.com/article28/iehjp.html

成都网站建设公司_创新互联，为您提供全网营销推广、标签优化、网站维护、建站公司、网站营销、微信小程序

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容