Portal

Portal1: AtCoder

Portal2: Luogu

Description

この問題は、講座用問題です。ページ下部に解説が掲載されています。

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

Input

入力は以下の形式で標準入力から与えられる。

$$H W \\ c_{0, 0} c_{0, 1} \cdots c_{0, w - 1} \\ c_{1, 0} c_{1, 1} \cdots 1_{0, w - 1} \\ \cdots \cdots \\ c_{H, 0} c_{H, 1} \cdots 1_{H, w - 1}$$

• $1$行目には、街の南北の長さとして整数$H(1 \le H \le 500)$と東西の長さとして整数$W(1 \le W \le 500)$が空白で区切られて与えられる。

• $2$行目からの$H$行には、格子状の街の各区画における状態$c_{i, j} (0 \le i \le H - 1, 0 \le j \le W - 1)$が与えられる。

  • $i$行目$j$文字目の文字$c_{i, j}$はそれぞれs, g, ., #のいずれかで与えられ、座標$(j, i)$が下記のような状態であることを表す。

    • s : その区画が家であることを表す。
    • g : その区画が魚屋であることを表す。
    • . : その区画が道であることを表す。
    • # : その区画が塀であることを表す。

  • 高橋君は家·魚屋·道は通ることができるが、塀は通ることができない。

  • 与えられた街の外を通ることはできない。

  • sとgはそれぞれ$1$つずつ与えられる。

Output

塀を$1$回も壊さずに、家から魚屋まで辿り着くことができる場合はYes、辿りつけない場合はNoを標準出力に$1$行で出力せよ。

Sample Input1

4 5
s####
....#
#####
#...g

Sample Output1

No

Sample Input2

4 4
...s
....
....
.g..

Sample Output2

Yes

Sample Input3

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

Sample Output3

No

Sample Input4

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

Sample Output4

Yes

Description in Chinese

高桥先生住的小区是长方形的，被划分成一个个格子。高桥先生想从家里去鱼店，高桥先生每次可以走到他上下左右四个格子中的其中一个，不能斜着走，也不能走出小区或穿墙。

地图语言解释：

• s：表示高桥先生的家（起始点）

• g：表示鱼店（终点）

• .：表示道路

• #：表示墙壁

Solution

我们不妨采用深度优先搜索，先在地图上找出起始点，然后用灌水法（将起始点能到达的地方标记），我是直接修改地图的，最后再扫描一边地图，看看终点还在不在，如果在就表示还没标记过，也就是走不到，输出No，如果终点不存在，也就是被标记了，就说明可以到达，输出Yes。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

const int MAXN = 505;
int n, m, stx, sty;
char map[MAXN][MAXN];
inline void dfs(int x, int y) {
    if (x < 1 || y < 1 || x > n || y > m) return ;//如果超越了边界
    if (map[x + 1][y] != '#' && map[x + 1][y] != '!') {//向右
        map[x + 1][y] = '!';
        dfs(x + 1, y);
    }
    if (map[x][y + 1] != '#' && map[x][y + 1] != '!') {//向下
        map[x][y + 1] = '!';
        dfs(x, y + 1);
    }
    if (map[x - 1][y] != '#' && map[x - 1][y] != '!') {//向左
        map[x - 1][y] = '!';
        dfs(x - 1, y);
    }
    if (map[x][y - 1] != '#' && map[x][y - 1] != '!') {//向上
        map[x][y - 1] = '!';
        dfs(x, y - 1);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 's') {
                stx = i; sty = j;//找出起始点并标记
            }
        }
    dfs(stx, sty);
    bool flag = 1;
    for (int i = 1; i <= n; i++) {//寻找终点有没有被标记过
        for (int j = 1; j <= m; j++)
            if (map[i][j] == 'g') {
                flag = 0;
                break;
            }
        if (!flag) break;
    }
    if (flag) printf("Yes\n"); else printf("No\n"); 
    return 0;
}