1215 迷宫

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2596 售货员的难题

    2596 售货员的难题 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 钻石 Diamond 题目描述 Description 某...

    attack
  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack
  • P1514 引水入城

    题目描述 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代...

    attack
  • 2596 售货员的难题

    2596 售货员的难题 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 钻石 Diamond 题目描述 Description 某...

    attack
  • 【POJ1456】Supermarket(贪心)

    每个商品有过期日期和价格,每天可以卖一个商品,必须在过期前出售才能收益,求最大收益。

    饶文津
  • C++的函数对象优于函数指针地方

    转载自:http://blog.csdn.net/huang_xw/article/details/7934156    

    Daotin
  • LeetCode第166场周赛题解

    这是LeetCode的第166场周赛的题解,不出意外的又爆炸了,前三题只做了20分钟,第4题因为题意读错了耽误了40分钟,到1小时15分钟左右才写完。排名直接1...

    BBuf
  • 位运算的方法,小结

    文章来源未知----再次声明为转载... 本文是针对使用位运算来实现一些方法,我们都知道位运算的代价比其他符号运算都低,所以当一个方法只使用位运算且运算次数与其...

    Gxjun
  • 1065. 单身狗(25)

    “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

    AI那点小事
  • SPOJ 375 边操作

    给一颗树,每条边有一个权值。有两种操作:1、修改某条边的值;2、询问a、b两点路径上边权的最大值。

    用户2965768

扫码关注云+社区

领取腾讯云代金券