WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
}