Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
 Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

其实BFS 不用记录路径

Posted by qrmajia at 2009-03-27 15:51:03 on Problem 1101 
 我昨天就是用记录路径搞,WA了好久,不能一步一步的走,
因为走的折线比较少的而可能走得慢,所以如果走得快的
而走得弯弯扭扭的把那个格子前标记掉了,走得慢的但走
的折线少的那条路就无法走了,不标记的话又肯定是不行
的,所以不要每次走一步,改走射线,BFS的时候把某一格前
面空的全部入队,再下一步,这样的话,最快到目的地的也
肯定是拆线最少的,而且折线的数量刚好是步数加1就OK了!
Followed by:
Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator