JOI本選過去問 第8回 日本情報オリンピック本選 4問目 散歩

問題分は「AOJ 0541」とでもググってください。

• DPでやりました。

• N-1回目までの散歩でそれぞれ何回その場所に通るか回数をdpに入れていき、その合計が偶数なら何もしない、奇数なら「南」「東」を反転させ、N回目をシミュレーションしていき感じです。

• おそらくもっともっといい解放があるはず。解説見てみます。

• これぐらいの難易度の問題なら考えれば解けるはずなので気合。

#include <cstdio>
#include <string.h>

using namespace std;


int h = 0,w = 0;

int n = 0;

int dp[1003][1003];

int d[1003][1003] = {0};

int main(){

  while(1){


  scanf("%d%d%d",&h,&w,&n);

  if(h == 0) break;

  memset(dp,0,sizeof(dp));

  memset(d,0,sizeof(d));

  for(int i = 1;i <= h;i++){
    for(int j = 1;j <= w;j++){
      scanf("%d",&d[i][j]);
    }
  }

  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 tmp1=0,tmp2=0;
      if(d[i][j-1] == 1) tmp1 = 1;
      dp[i][j] += (tmp1 + dp[i][j-1]) / 2;
      if(d[i-1][j] == 0) tmp2 = 1;
      dp[i][j] += (tmp2 + dp[i-1][j] ) / 2;
    }
  }


  for(int i = 1;i <= h;i++){
    for(int j = 1;j <= w;j++){
      if(dp[i][j] % 2 == 1){
	if(d[i][j] == 1){
	  d[i][j] = 0;
	}else{
	  d[i][j] = 1;
	}
      }
    }
  }

  int x = 1,y = 1;

  while(x <= w && y <= h){

    if(d[y][x] == 0){
      y++;
    }else{
      x++;
    }

  }

  printf("%d %d\n",y,x);
  }

  return 0;

}

変数説明

int h,w,n; => 問題文参照

int dp[i][j] => n-1回までで、散歩で(i,j)の場所に通る合計数。

int d[i][j] => (i,j)の情報（0 or 1)