AT_dfs_a 深さ優先探索

[problemUrl]: https://atcoder.jp/contests/atc001/tasks/dfs_a 本题为讲座用题目。页面下方附有题解。 高桥君居住的城市呈长方形，被划分为网格状的区块。长方形的每条边都与东西或南北方向平行。每个区块要么是道路，要么是围墙。高桥君只能在道路上沿东西南北方向移动，不能斜向移动。同时，围墙区块无法通过。 请判断高桥君能否在不破坏围墙的情况下，仅通过道路到达鱼店。

输入通过标准输入按以下格式给出。 > $ 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$ 行，每行包含 $W$ 个字符 $c_{i,j}$（$0 \leq i \leq H-1,\ 0 \leq j \leq W-1$），表示网格中每个区块的状态。 - 第 $i$ 行第 $j$ 个字符 $c_{i,j}$ 取值为 `s`、`g`、`.`、`#` 之一，表示坐标 $(j, i)$ 的区块状态： - `s` ：该区块为高桥君的家。 - `g` ：该区块为鱼店。 - `.` ：该区块为道路。 - `#` ：该区块为围墙。 - 高桥君可以通过家、鱼店和道路，但不能通过围墙。 - 不能走出给定城市的范围。 - `s` 和 `g` 各出现一次。

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

### 题解 **[深度优先搜索的染色法](https://www.slideshare.net/secret/lyag9AlTOMIY2J "深さ優先探索による塗りつぶし")** 来自 **[AtCoder Inc.](http://www.slideshare.net/chokudai)** ### 样例解释 1 高桥君无法到达鱼店。 由 ChatGPT 4.1 翻译