AOJ 0547 : Commute routes

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547

解法

各交差点に於ける状態は、以下の四つに分けられます。

• 右向きで曲がれる
• 上向きで曲がれる
• 右向きで曲がれない
• 上向きで曲がれない

これら四つの状態と、東西方向・南北方向の座標の三つの値で、状態を完全に表すことができます。
上記の状態に番号を割り振り、
dp[i][j][s] := 「 ( j, i ) で状態が s 」の状態に至る経路数
とする動的計画法で解くことができます。

動的計画法の部分について詳しく述べます。
まず、南端と西端の交差点を 1 と初期化します。
それ以外の一般の交差点については、状態毎に以下のようにして求まります。

• 右向きで曲がれる := 一つ左の交差点の、右向きで曲がれない状態と右向きで曲がれる状態の和
• 上向きで曲がれる := 一つ下の交差点の、上向きで曲がれない状態と上向きで曲がれる状態の和
• 右向きで曲がれない := 一つ左の交差点の、上向きで曲がれる状態
• 上向きで曲がれない := 一つ下の交差点の、右向きで曲がれる状態

最後に、座標 ( w, h ) の各状態の和を求めればそれが答えです。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

const int MOD = 100000;
enum { RIGHT_TURNABLE, UP_TURNABLE, RIGHT_STRAIGHT, UP_STRAIGHT };

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	while ( true )
	{
		int w, h;
		cin >> w >> h;

		if ( !( w | h ) )
		{
			break;
		}

		vector< VVI > dp( h, VVI( w, VI( 4, 0 ) ) );

		{ // initialize
			int m = max( h, w );

			REP( i, 1, m )
			{
				if ( i < h )
				{
					dp[i][0][ UP_TURNABLE ] = 1;
				}
				
				if ( i < w )
				{
					dp[0][i][ RIGHT_TURNABLE ] = 1;
				}
			}
		}

		REP( i, 1, h )
		{
			REP( j, 1, w )
			{
				dp[i][j][ RIGHT_TURNABLE ] += dp[i][ j - 1 ][ RIGHT_STRAIGHT ] + dp[i][ j - 1 ][ RIGHT_TURNABLE ];
				dp[i][j][ UP_TURNABLE ] += dp[ i - 1 ][j][ UP_STRAIGHT ] + dp[ i - 1 ][j][ UP_TURNABLE ];;
				dp[i][j][ RIGHT_STRAIGHT ] += dp[i][ j - 1 ][ UP_TURNABLE ];
				dp[i][j][ UP_STRAIGHT ] += dp[ i - 1 ][j][ RIGHT_TURNABLE ];

				REP( k, 0, 4 )
				{
					if ( MOD <= dp[i][j][k] )
					{
						dp[i][j][k] %= MOD;
					}
				}
			}
		}

		cout << accumulate( ALL( dp.back().back() ), 0 ) % MOD << endl;
	}
		
	return 0;
}