首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >1215 迷宫

1215 迷宫

作者头像
attack
发布2018-04-12 16:48:34
1.2K0
发布2018-04-12 16:48:34
举报

1215 迷宫

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

在N*N的迷宫内,“#”为墙,“.”为路,“s”为起点,“e”为终点,一共4个方向可以走。从左上角((0,0)“s”)位置处走到右下角((n-1,n-1)“e”)位置处,可以走通则输出YES,不可以走则输出NO。

输入描述 Input Description

输入的第一行为一个整数m,表示迷宫的数量。  其后每个迷宫数据的第一行为一个整数n(n≤16),表示迷宫的边长,接下来的n行每行n个字符,字符之间没有空格分隔。

输出描述 Output Description

输出有m行,每行对应的迷宫能走,则输出YES,否则输出NO。

样例输入 Sample Input

1 
7 
s...##. 
.#..... 
....... 
..#.... 
..#...# 
###...# 
......e

样例输出 Sample Output

YES

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开

裸dfs,注意这个不需要回退

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=1001;
 6 const int maxn=0x7fffffff;
 7 int map[MAXN][MAXN];
 8 int vis[MAXN][MAXN];
 9 int bgx,bgy;
10 int edx,edy;
11 int xx[5]={-1,+1,0,0};
12 int yy[5]={0,0,-1,+1};
13 int n;
14 int m;
15 int flag;
16 void dfs(int x,int y)
17 {
18     if(x==edx&&y==edy)
19     {
20         flag=1;
21         return ;
22     }
23     for(int i=0;i<4;i++)
24     {
25         int wx=x+xx[i];
26         int wy=y+yy[i];
27         if(wx>0&&wx<=m&&wy>0&&wy<=m&&map[wx][wy]!=1&&vis[wx][wy]==0)
28         {
29             vis[wx][wy]=1;
30             dfs(wx,wy);
31         }
32     }
33 }
34 int main()
35 {
36     
37     scanf("%d",&n);
38     for(int lll=1;lll<=n;lll++)
39     {
40         
41         scanf("%d",&m);
42         memset(vis,0,sizeof(vis));
43         for(int i=1;i<=m;i++)
44         {
45             for(int j=1;j<=m;j++)
46             {
47                 char c;
48                 //scanf("%c",&c);
49                 cin>>c;
50                 if(c=='.')map[i][j]=0;
51                 else if(c=='#')map[i][j]=1;
52                 else if(c=='s')
53                 {
54                     bgx=i;
55                     bgy=j;
56                 }
57                 else if(c=='e')
58                 {
59                     edx=i;
60                     edy=j;
61                 }
62             }
63         }
64         dfs(bgx,bgy);
65         if(flag==1)
66         printf("YES");
67         else 
68         printf("NO");
69     }
70     
71     return 0;
72 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-04-19 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1215 迷宫
    • 分类标签 Tags 点此展开
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档