作者flere (人间失格)
站内Prob_Solve
标题[问题] ICPC 6010
时间Sat Mar 2 07:26:19 2013
想跟大家讨论一下ICPC 6010 这一题的作法
题目网址 :
http://ppt.cc/fHLE
这一题看起来不难
可是比赛场上没有队伍过OAO
ICPC上面过的人也极少
所以我在想一定有些什麽地方我没弄懂或误会了OAQ
以下是题意:
给一个最大10*10的棋盘
"S"代表起始位置,"T"代表终点位置
"."不能走
"0"~"9"代表数字,可以走
现在给你一颗骰子(会给你他的长相,上面有哪些数字(只会出现1-6
比如说给你123465代表(右左前後上下
现在你要开始滚动这颗骰子从S到T
当你压到的数字跟你骰子底下的数字一样时,比如说都是5
这时你的分数可以加上(5+5)
当你压到的数字跟你的底部不一样时,假设你压到3,然後骰子底部是5
这时分数要扣(3+5)
起点S一旦离开就不能再走进去
一旦走到终点就结束
其他数字点皆可以无限走
问说
可以到终点吗?
可以的话最高能拿几分?
可以无限洗分吗??
以下是我的作法
step 1 : 我先从S做一次BFS看能不能到T,这边不行的话就可以直接输出impossible
step 2 : 把起点S标记成墙壁,因为他走出去之後就相当於变成墙壁了,这时从
终点T做一次BFS,看终点在S变成墙壁时可以走到那些点
所以之後滚动就只滚那些点就好了
不然有可能你走到一个地方分数能变高,但是因为起点不能重复走而走不到终点的情况
step 3 : 开始滚动,我用SPFA的作法从起点开始,若有一个点被更新超过(N*M)次,
表示侦测到正环->输出infinity
然後我记录的状态是
state[][][][][],前3格是骰子的样子,後两格为棋盘上的位置
不知道这样的方法哪边会出现问题??
还是各位有别的不同的想法吗??
感觉最不正确的是step 3....可是感觉跟判断负环是一样的道理> <
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 180.177.7.105
※ 编辑: flere 来自: 180.177.7.105 (03/02 07:27)
1F：→ scwg:三秒 200 个 case, graph size = 2400, 有难度.. 03/02 11:06
2F：→ flere:2400是??我这样是不会TLE,可是会WA> < 03/02 11:11
3F：→ DJWS:100(棋盘大小)*6(骰子底面)*4(骰子正面) 03/02 20:10
4F：→ DJWS:分数也列入状态就是2400*100*6*4*2(加分)*2(倒扣) 记忆体会爆 03/02 20:13
5F：→ DJWS:上面应该是2400*4(骰子来自方向)*6(点数)*4(加分倒扣) 03/02 20:22
6F：→ DJWS:所以记忆体应该存得下! 03/02 20:23