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した。何が悪かったのか分からない。