Codeforces #180, Division 2, B : Sail

問題文

http://codeforces.com/contest/298/problem/B

概要

帆に風を受けることによってのみ移動可能な船がある。
単位時間で、そのとき風が吹いている方向に 1 移動することができる。
船には碇がついており、碇を下ろすことでその時間には移動しないことができる。

時間 t の間に吹く風の情報が与えられるので、( sx, sy ) から ( ex, ey ) に移動するのにかかる最短の時間を求めよ。
移動が不可能な場合は -1 で示せ。

解法

一度ある方向に移動してから、逆の方向に移動する行為に意味はありません。
従って、目的地へのマンハッタン距離が小さくなる方向にのみ移動すればよいことになります。
ある方向への移動は早いうちに済ませてしまったほうがよいので、時間が早い方から貪欲に、移動できるときには移動するようにすれば解けます。
なお、-1 になるのは最後まで処理しても辿りつけなかった場合です。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

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

	int t, sx, sy, ex, ey;
	cin >> t >> sx >> sy >> ex >> ey;

	string winds;
	cin >> winds;

	if ( sx == ex && sy == ey )
	{
		cout << 0 << endl;
		return 0;
	}

	REP( i, 0, t )
	{
		char d = winds[i];
		if ( d == 'E' && sx < ex )
		{
			sx++;
		}
		else if ( d == 'W' && ex < sx )
		{
			sx--;
		}
		else if ( d == 'N' && sy < ey )
		{
			sy++;
		}
		else if ( d == 'S' && ey < sy )
		{
			sy--;
		}
		
		if ( sx == ex && sy == ey )
		{
			cout << i + 1 << endl;
			return 0;
		}
	}

	cout << -1 << endl;
	return 0;
}