以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 3 – Sokoban
倉庫番(Sokoban)
「倉庫番」は,長年人々に愛され続けてきているパズルである.
「倉庫番」は縦M 横N マスの正方形に区切られた盤面で行われる.盤面上に箱があり,プレイヤー ×
を操作して箱を目標地点へ動かすことが目的である.この問題では,箱が1 個である場合を考える.盤面
の一部のマスは壁であり,プレイヤー・箱・目標地点は壁でない1 マスに位置している(プレイヤーや箱は
盤面から出ることはない).以下のいずれかの操作が可能である.
プレイヤーがいるマスに隣接しているマスのうち壁でなく箱がないマスを1 つ選び,プレイヤーをそ •
のマスへ移動させる.
プレイヤーがいるマスと箱があるマスが隣接していて,さらに,箱のマスに隣接していてプレイヤー •
と反対側にある壁でないマスが存在するとき,箱をそのマスに動かし,プレイヤーを箱があったマス
に移動させる.
ここで,マスとマスが隣接しているとは,それらのマスが1 辺を共有することである.
以下に,「倉庫番」の問題の例を示す.文字# は壁,文字@ はプレイヤー,文字O は箱,文字X は目標地
点,文字. はその他のマス目を表している.
..#@.
.X.O.
##..#
この状態からは,以下の操作によって箱を目標地点へ動かすことができる.
1. プレイヤーを右に動かす.
2. プレイヤーを下に動かす.
3. 箱とプレイヤーを左に動かす.
4. 箱とプレイヤーを左に動かす.
一方,次の状態からは箱を目標地点へ動かすことはできない.
..#..
.X.O.
##.@#
あなたは,盤面の壁の位置と目標地点が決まっているとき,プレイヤーと箱を配置して,解ける「倉庫
番」の問題が何通りできるか知りたい.ここで,解ける「倉庫番」の問題とは,操作を何回か繰り返して箱
を目標地点へ移動させることができるような初期配置を指す.また,プレイヤーと箱はそれぞれ壁でなく
目標地点と異なるマスに配置しなければならず,プレイヤーと箱は異なるマスに配置しなければならない.
倉庫番– 1 / 3
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 3 – Sokoban
課題
盤面の大きさおよび盤面の壁の位置と目標地点が与えられたとき,解ける「倉庫番」の問題が何通りで
きるかを求めるプログラムを作成せよ.
制限
1 ≦M ≦1 000 盤面の縦の長さ
1 ≦N ≦1 000 盤面の横の長さ
入力
標準入力から以下の入力を読み込め.
1 行目には整数M, N が空白を区切りとして書かれており,それぞれ盤面の縦と横の長さを表す. •
続くM 行は盤面の情報を表す.各行はN 文字からなる.各文字は# X . のいずれかであり,文字# •
は壁,文字X は目標地点,文字. はその他のマス目(プレイヤーや箱の初期位置の候補でもある) を
表している.文字X はちょうど1 回現れる.
出力
標準出力に,解ける「倉庫番」の問題が何通りできるかを表す整数を1 行で出力せよ.
採点基準
採点用データのうち,配点の20%分については,M ≦50, N ≦50 を満たす.
入出力例
入力例1 出力例1
3 5 9
..#..
.X...
##..#
解ける「倉庫番」の問題は以下に示す9 通りが考えられる.
..#@. ..#.@ ..#.. ..#.. ..#.. ..#.. ..#@. ..#.@ ..#..
.XO.. .XO.. .XO@. .XO.@ .XO.. .XO.. .X.O. .X.O. .X.O@
##..# ##..# ##..# ##..# ##@.# ##.@# ##..# ##..# ##..#
倉庫番– 2 / 3
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 3 – Sokoban
入力例2 出力例2
2 3 0
.X.
...
この例では,解ける「倉庫番」の問題を作ることができない.
入力例3 出力例3
4 7 24
.#.#.##
##.#..#
....X..
##.#...
倉庫番– 3 / 3