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

POJ数据如何加强的,能通过官方数据但是不能通过POJ上的?

Posted by snoopy at 2006-09-19 11:26:20 on Problem 1199
我的程序可以通过去该赛区官方主页上下来的数据,但是在POJ上WA了,请指点

我的算法是一开始从最外围开始找一个入口,入口定义是存在一个可到达的点,该点不属于任何一个2*2的可到达区域(为了实现此目的,在原图外围添加了2层可到达的点),然后进行普通的DFS,如题目描叙,遇见一个岔路就向左,如果到达一个属于超过2*2的可到达区域的点,则说明到达了大厅(就是题目中要求的地方)

官方数据是可以往回走的,就是走到死路后可以转180'继续,在POJ上我提交过可以回走和不可以回走都错了.并且数据中应该是没有一个可到达环的情况的,因为如果出现此情况,我的程序会是TLE(根据走迷宫的一个定理)

我现在有怀疑自己程序的一个地方就是,可能在判断入口的地方会存在一个
.......x
###.###x
#.###.#x
xxxxxxxx
(迷宫剩余部分略)
的情况,这我会将第二行第四列判成一个入口而输出NO,不知道POJ上是否会有这种情况?

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