「省选模拟赛」[BZOJ1556] 小奇走迷宫

2015年12月19日7,0422

原题:「bzoj1556」墓地秘密

「题目背景」

小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫,一旁的木牌上写着:“你可以回头,但你永远无法离去。”

「问题描述」

木牌下方有一行小字:“撞击所有机关墙”。

G-1500机器人每次可以朝着前方光速移动,质量、动能无穷大,可以选择自己在行进中停下来或者撞墙后停下来,移动时只有转向需要花费时间。

真是个诡异的迷宫,不过,小奇的眼前已经出现了迷宫的地图,它想尽早离开这里,请你帮助小奇制定一个行动方案,使得转向的次数最小,且在行动时撞击过所有的机关墙。

「输入格式」

第一行包含三个正整数n,m,K,表示迷宫的大小为n*m,迷宫中有K个机关墙。

接下来给出一个n*m的矩阵,.表示空地,#表示墙。

接下来K行,每行包含两个正整数a,b,表示第a行第b列的墙是机关墙。

最后一行包含两个正整数x,y,表示小奇的起始位置在第x行第y列,为了方便,认为起始时机器人方向奇怪,需要转向一次。

「输出格式」

输出一个正整数,表示小奇撞击完机关墙的最少转向次数,保证问题有解。

「样例输入」

4 6 3

……

.#..#.

.#…#

….#.

2 2

3 6

4 5

1 5

「样例输出」

6

「数据范围」

对于10%的数据,n,m <= 10,1 <= K <= 2。

对于40%的数据,n,m <= 50,1 <= K <= 10。

对于100%的数据,n,m <= 100,1 <= K <= 15。

「提示」

迷宫的最外层是墙,所有墙都是基岩,无法破坏。

移动方向只能是四个基本方向之一。

「题解」

对于40%的数据

状压墙的撞击情况,然后广搜

d[x][y][st][dir]表示到x行y列,撞击情况为st,朝向为dir的最小转向数

对于100%的数据

只有机关四周的四个石头是有意义的

只会在这些格子间之间走最短路(可以广搜来求),那么只剩下4T个格子,预处理每个格子到另一个格子撞机关的最少转向次数

最后状压dp即可

复杂度4T*4NM+2^T*4T*4T

由于我预处理写的是spfa,会多花些时间

 

avatar
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
hzwer Recent comment authors
  Subscribe  
提醒
雨梦
雨梦

memset(dis,127/3,sizeof(dis));是什么意思啊?