AOJ 0541 散歩
解法
10^7回も散歩する太郎君の問題
解説みた。動的計画法を使う。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_HW = 1000; int N, H, W; int a[MAX_HW + 2][MAX_HW + 2]; int dp[MAX_HW + 2][MAX_HW + 2]; int main(){ while(scanf("%d %d %d", &H, &W, &N), N != 0){ for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) scanf("%d", &a[i+1][j+1]); dp[1][1] = N-1; for(int i = 1; i <= H; i++){ for(int j = 1; j <= W; j++){ if(i + j == 2) continue; int n, w; if(dp[i-1][j] % 2 == 0){ n = dp[i-1][j] / 2; }else{ if(a[i-1][j] == 0) n = (dp[i-1][j] + 1) / 2; else n = (dp[i-1][j] - 1) / 2; } if(dp[i][j-1] % 2 == 0){ w = dp[i][j-1] / 2; }else{ if(a[i][j-1] == 0) w = (dp[i][j-1] - 1) / 2; else w = (dp[i][j-1] + 1) / 2; } dp[i][j] = n + w; } } int y = 1, x = 1; while(true){ if(x > W || y > H) break; if(dp[y][x] % 2 == 0){ if(a[y][x] == 0) y++; else x++; }else{ if(a[y][x] == 0) x++; else y++; } } printf("%d %d\n", y, x); } return 0; }