AOJ 0541 Walk

このブログ、まだ最初の記事を一人の人に見られただけですｗ(☆つけられてないだけかもしれない)

解法

DP。dp[i] [j] ：= (i,j)をN-1回の散歩で何回通ったか。
苦手なDPなのでスラスラ書けるようになりたい＞＜

ソースコード

#include <cstring>
#include <iostream>
using namespace std;
int main()
{
	while(1)
	{
		int H,W,N;
		cin >> H >> W >> N;
		if(H==0&&W==0&&N==0)break;
		int mp[H+2][W+2];
		int dp[H+2][W+2];
		for(int i=0;i<H+2;i++)
		{
			for(int j=0;j<W+2;j++)
			{
				mp[i][j]=-1;
			}
		}
		memset(dp,0,sizeof(dp));
		dp[1][1]=N-1;
		for(int i=1;i<=H;i++)
		{
			for(int j=1;j<=W;j++)
			{
				cin >> mp[i][j];
			}
		}
		for(int i=1;i<=H;i++)
		{
			for(int j=1;j<=W;j++)
			{
				if(dp[i][j]%2==1)
				{
					if(mp[i][j]==0)
					{
						dp[i+1][j]+=(dp[i][j]+1)/2;
						dp[i][j+1]+=(dp[i][j]-1)/2;
					}
					else
					{
						dp[i][j+1]+=(dp[i][j]+1)/2;
						dp[i+1][j]+=(dp[i][j]-1)/2;
					}
				}
				else
				{
					dp[i+1][j]+=dp[i][j]/2;
					dp[i][j+1]+=dp[i][j]/2;
				}
			}
		}
		int i=1,j=1;
		while(1)
		{
			if(mp[i][j]==-1)break;
			if(mp[i][j]&&dp[i][j]%2)i++;
			else if(mp[i][j]&&!(dp[i][j]%2))j++;
			else if(!mp[i][j]&&dp[i][j]%2)j++;
			else i++;
		}
		cout << i << ' ' << j << endl;
	}
	return 0;
}