Codeforces #180 Div2 B "Sail"
問題
http://codeforces.com/contest/298/problem/B
訳
北極熊が魚釣りをしている。彼はボートで(sx, sy)から(ex, ey)へ移動しようと思っている。
しかし、このボートは風によってしか移動する事ができない。
一秒一秒、風は北向き・南向き・東向き・西向きのいずれかの方向に吹く。
現在(x, y)にボートがあると仮定すると、
- 東向きの風が吹いたとき、ボートは(x+1, y)へ移動する。
- 南向きの風が吹いたとき、ボートは(x, y-1)へ移動する。
- 西向きの風が吹いたとき、ボートは(x-1, y)へ移動する。
- 北向きの風が吹いたとき、ボートは(x, y+1)へ移動する。
代わりに、彼は碇でボートを固定する事が出来る。
この場合だと、ボートは(x, y)にとどまる。
t秒目の風の方向が与えられるので、(ex, ey)へ到達するときの最短の時間を出力せよ。
制約
1 <= t <= 10^5
-10^9 <= sx, sy, ex, ey <= 10^9
考えた事
風の向き:SESNW 0秒目 @ 1秒目 @ @ 2秒目 @@ @@ 3秒目 @@ @@ @@ 4秒目 @@ @@ @@ @@ 5秒目 @@@ @@@ @@@ @@@
上記のように行ける範囲が長方形で広がっていくので
その上下左右の辺の位置を毎秒更新していく。
長方形が初めて目的地を含んだ時点が答え。
ソースコード
int main() { int t, sx, sy, ex, ey; scanf( "%d %d %d %d %d", &t, &sx, &sy, &ex, &ey ); int T, B, L, R; T = B = sy; L = R = sx; int res; for( res = 0; ; res++ ){ // ng if( res > t ){ res = -1; break; } // ok if( L <= ex && ex <= R && B <= ey && ey <= T ){ break; } char d; cin >> d; switch( d ){ case 'N': T++; break; case 'S': B--; break; case 'E': R++; break; case 'W': L--; break; } } cout << res << endl; }