第８回日本情報オリンピック 本選 「散歩」

解法：
それぞれの座標に行く回数をn-1回分まで記録しておき、その回数が奇数だったら最初の文字（東、西）を反転させ、偶数の場合なにもしない。
最後にn回目の散歩の終わる座標を求めて出力。

計算量O(HW)。

#include <cstdio>


using namespace std;
int h,w,n;
int dp[1002][1002] = {0};
bool ch[1002][1002];

int main(){
 

  while(1){
  scanf("%d%d%d",&h,&w,&n);
  if(h == 0)break;
  
  for(int i = 1;i <= h;i++){
    for(int j = 1;j <= w;j++){
      int tmp;
      scanf("%d",&tmp);
      dp[i][j] = 0;
      if(tmp == 0)ch[i][j] = false;
      else ch[i][j] = true;
    }
  }
  
  dp[1][1] = n-1;
  
  for(int i = 1;i <= h;i++){
    for(int j = 1;j <= w;j++){
      if(i == 1 && j == 1)continue;
      int p = 0;
      if(ch[i-1][j] == false)p = 1;
      dp[i][j] += (dp[i-1][j] + p)/2;
      if(ch[i][j-1] == false)p = 0;
      else p = 1;
      dp[i][j] += (dp[i][j-1] + p)/2;
    }
  }
  
  for(int i = 1;i <= h;i++){
    for(int j = 1;j <= w;j++){
      if(dp[i][j] % 2 == 1){
	if(ch[i][j] == true){
	  ch[i][j] = false;
	}else{
	  ch[i][j] = true;
	}
      }
    }
  }
  int i = 1,j = 1;
  while(i <= h && j <= w){
    if(ch[i][j] == true){
      j++;
    }else{
      i++;
    }
  }
  
  printf("%d %d\n",i,j);
  }
  
  return 0;