Problem H

Problem H: Slippy Floors
Problem setter: T. Muranushi
Slides: Y. Izumi
Talk: D. Mikurube
Problem Statement
......#############...........
....##_____________#..........
...#________________####......
..#________####_________#.....
.#________#....##________#....
#_________#......#________#...
#__________###...#_____^^_#...
.#__________A_#...#____^^_#...
8
8
..#___________#...#_>__###....
...###########.....####.......
How to Solve
 幅優先探索または反復深化探索
反復深化のほうが計算空間的には望ましい．
 王女の次の位置に雪だるまを配置
配置する／しないで分岐する．
 王女が過去に通った場所には配置しない
過去の通り道をふさいではいけない．
 どちらかといえば実装問題
Example Input
###########
#######
####
#>#___#___#
#__#__#
#A>#
#_#_#_#_#_#
#_____#
####
#___#___#_#
##___##
#########_#
#__^__#
#___#___#_#
#>_#_A#
#_#_#_#_#_#
#######
#_#___#___#
#_#########
#_#___#___#
#_#_#_#_#_#
#___#___#A#
 本当はもっと大きい（27×29）
###########

Download Report