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; }