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) --
GD Star Rating
loading...
248 wordsloading...
Last Post: Absolute keyword in Delphi
Next Post: Unspecified Error in Delphi 2007 on Windows 8