想跟大家讨论一下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....可是感觉跟判断负环是一样的道理> <

三秒 200 个 case, graph size = 2400, 有难度..

2400是??我这样是不会TLE,可是会WA> <

100(棋盘大小)*6(骰子底面)*4(骰子正面)分数也列入状态就是2400*100*6*4*2(加分)*2(倒扣) 内存会爆上面应该是2400*4(骰子来自方向)*6(点数)*4(加分倒扣)所以内存应该存得下!