Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 10 Contest LoginRegister Exam
2017 ACM 集训队预选排名~      报名入口
SDIBT Online Judge WebBoard
[ New Thread ]
Problem 2388 >> 2388DFS+剪枝
wl10174102 @ 2013-07-28 17:15:13
[ Quote ] [ Edit ] [ Delete ] 1#
优化1

不走死胡同!所谓死胡同,就是走进去以后就再也无法走出来的点。

一种简单的想法是:"任意时刻,必须保证和当前所在位置不相邻的未经点至少有两个相邻的未经点"。基于这种想法,可以采取这样的优化:

1、当前点周围的点D,如果只有一个与D相邻的未经点,则点D为必经点。
2、显然,如果当前点周围有两个或两个以上的符合上述条件的必经点,则无论走哪个必经点都会造成一个死胡同,需要剪枝。
3、如果当前点周围只有一个必经点,则一定要走到这个点。
4、如果该点周围没有必经点,则需要枚举周围每一个点。

该优化的力度很大,可以在0.2秒内解决N=6,但N=7仍然需要2秒左右的时间。
优化2

不要形成孤立的区域!如果行走过程中把路一分为二,那么肯定有一部分再也走不到了,需要剪枝。

形成孤立的区域的情况很多,如果使用Floodfill找连通块,代价会很大,反而会更慢。我只考虑了一种最容易出现特殊情况,即:

1、当前点左右都是已经点(包括边缘),而上下都是未经点
2、当前点上下都是已经点(包括边缘),而左右都是未经点

这样就会形成孤立的区域,只要将出现这种情况的状态都剪掉即可。
[Top]  [Previous]  [Next]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin