← 返回题目列表

AtCoder · joisc2012_sokoban

sokoban. 推箱子

中文机器翻译题面 查看原题

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

倉庫番 - 原题 PDF 第 1 页
原题PDF第8页
倉庫番 - 原题 PDF 第 2 页
原题PDF第9页
倉庫番 - 原题 PDF 第 3 页
原题PDF第10页
可复制的 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