AOJ : 0541 - Walk

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0541&lang=jp
日本語の問題文があるので省略

アルゴリズム

各マスを辿る回数をDPによって求めれば、一番最後、マスを乗ったときに行くべき方向が確定できる。
この情報があれば、最終的に行き着く先も確定できる。

プログラム

#include <stdio.h>
#include <string.h>

int t[1002][1002];
int dp[1002][1002];

int main(void){
  int i,j,ti,tj;
  int w,h,n;
  int d,gx,gy;

  while(scanf("%d%d%d",&h,&w,&n) && (h||w||n)){
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
        scanf("%d",&t[i][j]);
      }
    }

    memset(dp,0,sizeof(dp));
    dp[0][0] = n;
    gx = 0, gy = 0;

    for(tj=0;tj<w && gx<w && gy<h;tj++){
      for(i=0;i<h && 0<=tj-i && gx<w && gy<h;i++){
        d = 0;
        j = tj - i;

        if(dp[i][j] % 2 == 0){
          d = !t[i][j];
          dp[i][j+1] += dp[i][j] / 2;
          dp[i+1][j] += dp[i][j] / 2;
        }
        else{
          d = t[i][j];
          dp[i][j+1] += dp[i][j] / 2 + d;
          dp[i+1][j] += dp[i][j] / 2 + !d;
        }
        if(gx == j && gy == i){
          gx += d;
          gy += !d;
        }
      }
    }

    for(ti=1;ti<h && gx<w && gy<h;ti++){
      for(tj=0;tj<w && ti+tj<h && gx<w && gy<h;tj++){
        d = 0;
        i = ti + tj;
        j = w - tj - 1;

        if(dp[i][j] % 2 == 0){
          d = !t[i][j];
          dp[i][j+1] += dp[i][j] / 2;
          dp[i+1][j] += dp[i][j] / 2;
        }
        else{
          d = t[i][j];
          dp[i][j+1] += dp[i][j] / 2 + d;
          dp[i+1][j] += dp[i][j] / 2 + !d;
        }
        if(gx == j && gy == i){
          gx += d;
          gy += !d;
        }
      }
    }

    printf("%d %d\n",gy+1,gx+1);
  }

  return 0;
}