hrbust 2270 从前的宝藏

2019-11-06 08:03:36

字体：大中小

来源：转载

供稿：网友

从前的宝藏

Time Limit: 10000 MS

Memory Limit: 32768 K

Total Submit: 128(40 users)

Total Accepted: 38(35 users)

Rating:

Special Judge: No

Description

从前有一个藏宝图,“s”代表起点,“t”代表终点,“#”代表墙(墙不可以通过),“$”代表传送门(传送门之间可以直接到达),“*”代表空地。可不可以从起点到达终点,如果能输出“YES”,否则输出“NO”。

Input

输入数据有多组。每组数据第一行输入n, m带表地图的行数和列数(2 ≤ n + m ≤ 100)。接下来n行每行输出m个字母表示每个点的情况。数据保证:1. 保证地图上只有's', 't', '#', '$', '*'。2. 保证起点和终点有且只有一个。

Output

每组数据的输出有一行,如果能到达终点输出“YES”,否则输出“NO”。

Sample Input

1 2st5 5s******$**#####**$******t5 5s*********#####*********t

Sample Output

YESYESNO

深搜广搜都可以#include <stdio.h>#include <string.h>#include <algorithm>#include <stdlib.h>#include <iostream>using namespace std;#define ll long long int#define N 105int n,m,xx,yy;///定义地图长宽和一个记录终点坐标的变量char mp[N][N];int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};///定义上下左右四个方向int flag[N][N];///用来判断是否走过int ff(int i,int j)///第三步{ int dx,dy,x; for(x=0; x<4; x++) { dx=i+dir[x][0]; dy=j+dir[x][1]; if(dx>=0&&dx<n&&dy>=0&&dy<m)///同理，在终点开始搜索传送门 { if(mp[dx][dy]=='*'&&flag[dx][dy]!=1) { flag[dx][dy]=1; ff(dx,dy); } else if(mp[dx][dy]=='$') { flag[xx][yy]=1; break; } else continue; } }}int DFS(int i,int j)///第二步{ int dx,dy,x; for(x=0; x<4; x++) { dx=i+dir[x][0];///将起点坐标带入，然后运用递归上下左右走 dy=j+dir[x][1]; if(dx>=0&&dx<n&&dy>=0&&dy<m)///如果没超出边界 { if(mp[dx][dy]=='*'&&flag[dx][dy]!=1)///如果是路，更新你现在的坐标，在这个基础上继续上下左右走，并将你走过的点标记 { flag[dx][dy]=1; DFS(dx,dy); } else if(mp[dx][dy]=='t')///如果到达终点，把终点标记为一，一会判断1，0就好 { flag[dx][dy]=1; } else if(mp[dx][dy]=='$')///如果搜到传送门，从终点那头也寻找传送门 { ff(xx,yy); } else continue; } }}int main()///第一步{ while(cin>>n>>m) { for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>mp[i][j]; if(mp[i][j]=='t') { xx=i,yy=j;///输入地图，然后记录下终点坐标 } } } memset(flag,0,sizeof(flag));///将flag数组清零 for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(mp[i][j]=='s')///搜到起点，开始搜索； DFS(i,j); } } if(flag[xx][yy]==1)///如果终点被标记为一，输出yes { cout<<"YES"<<endl; } else cout<<"NO"<<endl; }}

上一篇：5-9 用天平找小球 (10分)

下一篇：基于注解@Aspect的AOP实现

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注