【省选模拟赛】[bzoj1556]小奇走迷宫

2015年12月19日1,9092

原题:【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,会多花些时间