CF540C Ice Cave 题解

Description

Luogu传送门

Codeforces传送门

题目翻译有一点问题，应该是问能否掉进终点。

Solution

考虑直接 dfs，蒟蒻第一遍写时，是先从搜到起点搜到终点，然后再从终点开始搜，判断能否搜回来，然而…… Time limit exceeded on test 14

然后我就想为什么会 T，后来我发现搜到终点之后就不用再搜了，直接判断终点的上下左右有没有好冰即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, flag;
char s[510][510];
int sx, sy, ex, ey;
int vis[510][510];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

inline bool judge(int x, int y){
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

inline int check(int x, int y){//判断 (x, y) 上下左右有没有好冰
    if(vis[x][y] == 2) return 1;//自己就是碎冰，直接 YES
    for(int i = 0; i < 4; ++i){
        int mx = x + dx[i];
        int my = y + dy[i];
        if(judge(mx, my) && !vis[mx][my]) return 1;
    }
    return 0;
}

inline void dfs(int x, int y){
    if(flag) return;
    if(x == ex && y == ey)//到终点直接判
        return flag = check(x, y), void();
    for(int i = 0; i < 4; ++i){//向 4 个方向搜索
        int mx = x + dx[i];
        int my = y + dy[i];
        if(judge(mx, my) && (!vis[mx][my] || (mx == ex && my == ey))){//没有走过的点 或 终点
            vis[mx][my]++;
            dfs(mx, my);
        }
    }
    return;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= m; ++j)
            vis[i][j] = (s[i][j] == 'X');//把为碎冰的点 vis 初值赋为 1，表示不能走了。
    }
    scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
    dfs(sx, sy);
    puts(flag ? "YES" : "NO");
    return 0;
}

End