题库
题目列表
题单列表
题目收藏
记录
比赛
公开的比赛
我参与的比赛
用户
用户排名
近期排名
外部排名
用户对比
用户组列表
博客
集训队
赛事新闻
赛事列表
获奖情况
视频列表
登录
⭐关于举办浙江师范大学第23届大学生程序设计竞赛的通知
1215:迷宫
1 Sec
64 MB
|
Markdown
显示标签
简单
(*1000)
OI课程题库
DFS
206
441
通过
提交
题目描述
一天 Extense 在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由 $n\times n$ 的格点组成,每个格点只有两种状态,`.` 和 `#`,前者表示可以通行,后者表示不能通行。同时当 Extense 处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上。 Extense 想要从点 $A$ 走到点 $B$,问在不走出迷宫的情况下能不能办到。 如果起点或者终点有一个不能通行(为 `#`),则当作无法办到。
输入格式
第一行包含一个整数 $T\ (T\le 45)$,表示数据组数。 每组数据第一行包含一个正整数 $n\ (1\le n\le 100)$. 其后 $n$ 行,每行包含 $n$ 个字符,表示一个 $n\times n$ 的字符矩阵,矩阵仅由 `.` 和 `#` 组成。 最后一行包含 $4$ 个整数 $h_a,l_a,h_b,l_b$,表示 $A$ 点位于第 $h_a$ 行第 $l_a$ 列,$B$ 点位于第 $h_b$ 行第 $l_b$ 列。注意行列是从 $0$ 开始计数的。
输出格式
对于每组数据,在一行内输出一个字符串,如果能从点 $A$ 走到点 $B$,输出 `YES`,否则输出 `NO`。
样例输入 #1
复制
2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0
样例输出 #1
复制
YES NO
来源
一本通1215
题面
提交
记录
统计
上一题
下一题
上传者
coach
创建时间
2023-02-14 13:22
修改时间
2023-02-18 18:23
Markdown 题面
×
登录
×
账号
密码
记住我