| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1306 人关注过本帖
标题:zoj2749求思路
取消只看楼主 加入收藏
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
结帖率:94.44%
收藏
已结贴  问题点数:100 回复次数:6 
zoj2749求思路
想了4个多小时 各种超时啊, 求思路啊,求思路, 有AC的代码最好了, 可以用来研究,

 第一个贴AC代码的100分归他, 附上思路另加分啊
http://acm.zju.


我的思路是这样的 用DFS来搜
void DFS(int x, int y, int str[], int step, int val[10][5],int tmpp)

x,y 表示点坐标
step用来存步数
str用来存路径  (既存当前点的上一个点,像链表形式方式那样来存)
val[][0] val[][1] val[][2] 用来存每行0,1,2的个数
val[][4]用来存当前行已经访问过的那类数(这是用来剪支用的  如果当前行访问过了1就不能访问2的点了  反之也一样)
tmpp 是用来压缩存每行时候都已经是0和1 或0和2了  是就在相应的行号位上标记为1

然后加了两个普通的剪支方法:
 if(step + abs(x2-x) +abs(y2-y) >= tmpnum) return;
 if(step >= tmpnum) return; 其中tmpnum是存上次收到结果时的最小步数,x2,y2是目标坐标


然后就各种超时啊  是不是我思路原本就错了  还是没有想到犀利的剪支方法啊, 求解啊
搜索更多相关主题的帖子: 100分 void 最好 
2012-04-09 22:49
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 4楼 卧龙孔明
就是先构图, 再一次DFS是吧
2012-04-10 08:33
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
以下是引用卧龙孔明在2012-4-9 23:00:51的发言:

枚举每一横行最终变成白色还是黑色,然后验证一下变色的方格是否组成了一条不自交的线就可以了



"验证一下变色的方格是否组成了一条不自交的线"
这有什么算法不啊 我图构好用DFS回溯来判断还是TL
2012-04-10 13:28
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 8楼 卧龙孔明
DFS一次不行的吧, 他是要一条线啊
不回溯到达终点是不一定包含所有的点啊, 不是么??

还有我一开始题目读错了  以为要输出满足条件的最短的那条- -!
不过读对了还是超时, 孔明先生,要不给个AC代码让我研究研究啊
2012-04-10 20:59
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 10楼 卧龙孔明
连通性状态压缩dp   求指导啊
2012-04-11 09:05
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 14楼 czz5242199
没问题的, 只要可行解就可以, 我刚开始看错了, 一直在求最优解,呵呵
4天过去了,还是不会啊
2012-04-13 14:28
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 16楼 beyondyf
我第一次写就用你说的剪枝了, 可是TL了,  可能我代码写的撮了点也有关系
2012-04-14 19:28
快速回复:zoj2749求思路
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.012967 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved