AOJ 0541: Walk

愚直に全てシミュレーションするとTLEするので、N-1回散歩した後の地図を求めます。
ある点をn回通るとき、
(i) nが偶数のとき、東と南にn/2回ずつ通る
(ii)nが奇数のとき、最初に書かれていた文字の方向に(n+1)/2回、もう一方に(n-1)/2回通る
よって、通過する回数を動的計画法で計算すれば良いです。

通った回数だけ反転し、最後にシミュレーションすれば解けます。

#include<cstdio>
#include<cstring>
using namespace std;

int dp[1001][1001],g[1000][1000];

int main(){
	int H,W,N;
	while(scanf("%d%d%d",&H,&W,&N),H){
		memset(dp,0,sizeof(dp));
		memset(g,0,sizeof(g));
		
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				scanf("%d",g[i]+j);
			}
		}
		N--;
		dp[0][0] = N;
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				dp[i][j+1] += (dp[i][j]+ g[i][j])>>1;
				dp[i+1][j] += (dp[i][j]+!g[i][j])>>1;
			}
		}
		
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				g[i][j] ^= dp[i][j]&1;
			}
		}
		
		int y = 0,x = 0;
		while(y<H && x<W){
			if(g[y][x])x++;
			else y++;
		}
		
		printf("%d %d\n",y+1,x+1);
	}
	return 0;
}