AT_dfs_a.深さ優先探索

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

本题为讲座用题目。页面下方附有题解。

高桥君居住的城市呈长方形，被划分为网格状的区块。长方形的每条边都与东西或南北方向平行。每个区块要么是道路，要么是围墙。高桥君只能在道路上沿东西南北方向移动，不能斜向移动。同时，围墙区块无法通过。

请判断高桥君能否在不破坏围墙的情况下，仅通过道路到达鱼店。

输入通过标准输入按以下格式给出。

$ H $ $ W $
$ c_{0,0} $ $ c_{0,1} $ ... $ c_{0,W-1} $
$ c_{1,0} $ $ c_{1,1} $ ... $ c_{1,W-1} $
:
$ c_{H-1,0} $ $ c_{H-1,1} $ ... $ c_{H-1,W-1} $

第 $1$ 行包含两个整数 $H$ （城市南北方向长度， $1 \leq H \leq 500$ ）和 $W$ （东西方向长度， $1 \leq W \leq 500$ ），以空格分隔。
接下来的 $H$ $H$ 行，每行包含 $W$ $W$ 个字符 $c_{i,j}$ $c_{i, j}$ （ $0 \leq i \leq H-1,\ 0 \leq j \leq W-1$ $0 \leq i \leq H - 1, 0 \leq j \leq W - 1$ ），表示网格中每个区块的状态。
- 第 $i$ $i$ 行第 $j$ $j$ 个字符 $c_{i,j}$ $c_{i, j}$ 取值为 s、g、.、# 之一，表示坐标 $(j, i)$ $(j, i)$ 的区块状态：
  - s ：该区块为高桥君的家。
  - g ：该区块为鱼店。
  - . ：该区块为道路。
  - # ：该区块为围墙。
- 高桥君可以通过家、鱼店和道路，但不能通过围墙。
- 不能走出给定城市的范围。
- s 和 g 各出现一次。

如果能够在不破坏任何围墙的情况下，从家到达鱼店，输出 Yes；否则输出 No。输出仅一行。

输入#3

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
###.#.#.#.
#.....#...

输出#3

No

输入#4

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

输出#4

Yes

深度优先搜索的染色法 来自 AtCoder Inc.

高桥君无法到达鱼店。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?