111qqz的小窝

老年咸鱼冲锋!

whust #0.2 J Jailbreak (未AC)

J
19
Jailbreak
John is on a mission to get two people out of prison. This particular prison is a one-story
building. He has managed to get hold of a detailed floor plan, indicating all the walls and
doors. He also knows the locations of the two people he needs to set free. The prison guards
are not the problem – he has planned a diversion that should leave the building practically
void.
The doors are his main concern. All doors are normally opened remotely from a control
room, but John can open them by other means. Once he has managed to open a door, it
remains open. However, opening a door takes time, which he does not have much of, since
his diversion will only work for so long. He therefore wants to minimize the number of doors
he needs to open. Can you help him plan the optimal route to get to the two prisoners?
Input
On the first line one positive number: the number of test cases, at most 100. After that per test
case:
• one line with two space-separated integers h and w (2 ≤ h, w ≤ 100): the width and
height of the map.
• h lines with w characters describing the prison building:




‘.’ is an empty space.
‘ * ’ is an impenetrable wall.
‘#’ is a door.
‘$’ is one of the two people to be liberated.
John can freely move around the outside of the building. There are exactly two people on the
map. For each person, a path from the outside to that person is guaranteed to exist.
Output
Per test case:
• one line with a single integer: the minimum number of doors John needs to open in
order to get to both prisoners.20
Problem J: Jailbreak
Sample in- and output
Input Output
3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*…*…*
*$*.*.*.*.*
*…*…*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
********* 4
0
9

 

我的思路是这样的

先从两个人质出发做两遍bfs,做bfs的时候要记录路径

由于出口最多有400个(不到400)

然后枚举两个人质都能到达的出口

从两个人质到达该出口有两条路径

然后标记这两条路径上的门(注意重复的只标记一次)

然后统计门的数量.

然而wa了….

并不明白为什么.

改日再说.

View Code

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363