mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #301 (Div. 2) C. Ice Cave

Codeforcesの練習はじめました。いきなりひどい目にあった…

解法

変にある程度greedyできる解が見えるから良くない(ACするまでにunionFindとか全探索してから場合分けとかいろいろやってしまった)。

賢くやろうとせずに全探索で素直に解きましょう。今の氷の状態をstateで表し(1だったらまだ割れてない,2だったら割れてる)て,場合に応じてうまいことdfsしてやれば良い。そこはコード見てください。

int r1, c1, r2, c2;
int n, m;

int state[555][555];

void dfs(int r, int c) {
    if (r == r2 && c == c2 && state[r][c] == 2) {
        cout << "YES" << endl;
        exit(0);
    }
    if (r < 0 || r >= n || c < 0 || c >= m || state[r][c] == 2) return;
    state[r][c]++;
    for (int k = 0; k < 4; k++) dfs(r+dy[k], c+dx[k]);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            state[i][j] = (c == '.') ? 1 : 2;
        }
    }
    cin >> r1 >> c1;
    cin >> r2 >> c2;
    r1--; c1--;
    r2--; c2--;
    state[r1][c1]--;
    dfs(r1, c1);
    cout << "NO" << endl;
    return 0;
}