Codeforces: 298B Sail

The problem is from codeforces: http://codeforces.com/problemset/problem/298/B

The note given in the problem description pretty much explains the problem clearly. In every moment, the ship can choose to stay put or follow the direction instruction (wind). After given list of instructions, you need to check whether the ship can move to the destination.

The problem asks for the earliest time, which is the shortest path between two points. Therefore, the greedy approach provides the optimal solution. Always move a little bit closer to the final destination. If it is the opposite direction, then just throws the anchor (stay still).

#!/usr/bin/env python

n, sx, sy, ex, ey = map(int, raw_input().split())

cnt = 0
flag = False
for i in raw_input().strip():
    if ex > sx:
        if i == 'E':
            sx += 1
    elif ex < sx:
        if i == 'W':
            sx -= 1
    if ey > sy:
        if i == 'N':
            sy += 1
    elif ey < sy:
        if i == 'S':
            sy -= 1
    cnt += 1
    if sx == ex and sy == ey:
        print cnt
        flag = True
        break    
    
if not flag:
    print -1

--EOF (The Ultimate Computing & Technology Blog) --