AOJ 1144: Curling 2.0

問題

Curling 2.0 | Aizu Online Judge

• カーリングっぽいゲームを10回以内でクリアできるか調べよ

方針

• シミュレーションして10回以内にクリアできるか調べる
• 障害物にぶつかったら消去するという盤面変化を記録する方法がbfsだと思いつかなかったのでdfsして最小値を求めることにした

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

int w, h, a[21][21];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};

int INF = numeric_limits<int>::max();

int dfs(int y, int x, int cnt) {
    if(cnt == 10) return INF;
    int ret = INF;
    rep(i, 4) {
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(ny<0 || ny>=h || nx<0 || nx>=w ||
           a[ny][nx] == 1) continue;
        while(ny>=0 && ny<h && nx>=0 && nx<w) {
            if(a[ny][nx] == 3) {
                ret = min(ret, cnt+1);
                break;
            }
            if(a[ny][nx] == 1) {
                a[ny][nx] = 0;
                ret = min(ret, dfs(ny-dy[i], nx-dx[i], cnt+1));
                a[ny][nx] = 1;
                break;
            }
            ny += dy[i];
            nx += dx[i];
        }
    }
    return ret;
}

int main(void){
    while(cin >> w >> h && w && h) {
        rep(i, h) rep(j, w) cin >> a[i][j];
        rep(i, h) rep(j, w) if(a[i][j]==2) {
            int ans = dfs(i, j, 0);
            if(ans==INF) cout << -1 << endl;
            else cout << ans << endl;
        }
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1903131

反省

NEW GAME!放送までに間に合わせようと焦っていた間はWAだったが、NEW GAME!を見終わって新入社員の気持ちでイチから書き直したらACした。何が悪かったのか分からない。