Go across (ZOJ Problem Set - 3559)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3559

問題

矩形の毒沼がn個ある所でスタートからゴールまで行きたい。毒沼に入らず(境界含む)にゴールまで行くには最低何回曲がらないといけないか答えよ。
0<=n<=500

座標

<=10000

解法

座標圧縮してダイクストラ。整数座標以外でも曲がれることに注意。