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