| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:请高手提示In Reply To:请高手提示 Posted by:wzpwzpwzp at 2005-02-06 12:08:58 晕,花了好长时间,终于把题目的意思弄明白了,其实清楚了之后
就挺简单的。 说下我的理解:
问题:在1 ~ T时刻中,每一时刻t,请你确认该时刻的土匪在城市的
哪个点。所以使用三维图map[t][y][x]--y表示列方向。其中如
果值为1,则表示该位置(y,x)在t时刻被检查过,不会有土匪。
关键:小偷每个单位时间可以向4个方向移动一步,或者不移动。而
根据读入数据设置好map之后,这一时刻 t 的map[t][j][i]
肯定只有部分被确认为1,如何确认这一时刻t的所有没有被确认
过的map[t][j][i]?需要从当前t的两个时间方向t-1, t+1的map
取值来确认当前t的map[t][j][i]取值。而每个时间方向,
土匪就可能来自5个点了。根据t-1或t+1的5点取值来判定t的
取值。只要某个点的取值为0,则该t时刻没有被确认的点的
取值就是0;
最后:计算好整个map后。每一时刻都进行判断一次判断,对于某一
时刻t的map,只有一个点的值为0时,这才是土匪此时刻在的
位置,输出之。否则多个点的值为0,那么该时刻就无法判定。
搜索到最后,如果整个三维图都是 1, 都被检查没找到土匪呢,
土匪肯定跑掉了;否则,如果前面没有一次输出土匪的坐标,
那表示1~T任一时刻都无法确认土匪的位置,所以这些信息都是
"Nothing known."
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator