← 返回题目列表

AtCoder · joisc2016_j

J. 危险的滑冰

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

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

危険なスケート - 原题 PDF 第 1 页
原题PDF第1页
危険なスケート - 原题 PDF 第 2 页
原题PDF第2页
危険なスケート - 原题 PDF 第 3 页
原题PDF第3页
危険なスケート - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                Contest Day 4 – Dangerous Skating


             危険なスケート(Dangerous Skating)



  JOI 君は大自然の広大なスケートリンクでアイススケートをするのが趣味である.
 スケートリンクは南北にR マス,東西にC マスからなる長方形で表される.北からr 行目,西からc 列目
のマスをマス(r, c) と書くことにする.それぞれのマスはJOI 君が通過可能なマスであるか,氷塊があって通
過不可能なマスであるかのいずれかである.また,スケートリンクの外周のマスにはすべて氷塊があり,リ
ンクの外に出てしまうことはない.すなわち,マス(i, 1), (i,C) (1 ≦i ≦R) およびマス(1, j), (R, j) (1 ≦j ≦C)
には氷塊がある.
  JOI 君はあまりスケートがうまくない.JOI 君はスケートリンク上で移動するときは,東西南北のうち1
つの方向に向かってリンクの現在JOI 君がいるマスを蹴り,氷塊にぶつかる直前のマスまで進んで止まる.
リンクを蹴ってから止まるまでを1 回の移動と数える.隣接するマスに氷塊があるときは,その方向には
移動できない.
 ある日JOI 君がスケートを楽しんでいると,なんと,JOI 君がリンクを蹴ると,そのマスに氷塊が生えて
くることに気がついた.リンクを蹴った地点以外で通過したマスには氷塊は生えない.この状態でスケー
トを続けるのは非常に危険なので,JOI 君はできるだけ早くこのスケートリンクから脱出したい.
  JOI 君の現在地はマス(r1, c1) である.このスケートリンクから脱出するには,出口のマス(r2, c2) で止ま
る必要がある.JOI 君が安全にスケートリンクから脱出できるよう,現在地から移動を開始して出口のマ
スで止まるには,少なくとも何回の移動が必要かを計算するプログラムを書いてほしい.スケートリンク
の状態やJOI 君の現在地によっては,JOI 君がどのように移動しても出口のマスに止まることができない
こともあるかもしれない.JOI 君が移動の途中に出口のマスを通過しただけでは,スケートリンクからは
脱出できないことに注意せよ.


課題

 スケートリンク上の氷塊の情報と,JOI 君の現在地,出口のマスの位置が与えられたとき,JOI 君が現在
地から移動を開始して出口のマスで止まることができるかどうかを判定し,できる場合は,そのために必
要な移動回数の最小値を求めるプログラムを作成せよ.


入力

 標準入力から以下のデータを読み込め.

   • 1 行目には,整数R,C が空白を区切りとして書かれている.これは,スケートリンクの大きさが南
   北にR マス,東西にC マスであることを表す.

   • 続くR 行のそれぞれには,C 文字からなる文字列が書かれている.各文字は‘.’ または‘#’ のいずれ
   かである.このR 行のうちのr 行目(1 ≦r ≦R) の左からc 文字目(1 ≦c ≦C) は,スケートリンクの
    マス(r, c) の初期状態を表す.この文字が‘.’ のときは,そのマスが通行可能であることを表し,こ
   の文字が‘#’ のときは,そのマスに氷塊があって通行不可能であることを表す.



                    危険なスケート– 1 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                Contest Day 4 – Dangerous Skating


   • 続く1 行には,整数r1, c1 が空白を区切りとして書かれている.これは,JOI 君の現在地がマス(r1, c1)
   であることを表す.

   • 続く1 行には,整数r2, c2 が空白を区切りとして書かれている.これは,スケートリンクの出口がマ
     ス(r2, c2) であることを表す.


出力

 標準出力に,JOI 君が現在地から移動を開始して出口のマスで止まるために必要な移動回数の最小値を
表す整数を1 行で出力せよ.ただし,JOI 君がどのように移動しても出口のマスで止まることができない
場合は,-1 を出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 3 ≦R ≦1 000.

   • 3 ≦C ≦1 000.

   • 1 ≦r1 ≦R.

   • 1 ≦c1 ≦C.

   • 1 ≦r2 ≦R.

   • 1 ≦c2 ≦C.

   • スケートリンクの外周のマスにはすべて氷塊がある.すなわち,マス(i, 1), (i,C) (1 ≦i ≦R) およびマ
    ス(1, j), (R, j) (1 ≦j ≦C) には氷塊がある.

   • マス(r1, c1) およびマス(r2, c2) に氷塊はない.


小課題

小課題1 [13 点]

 以下の条件を満たす.

   • R ≦10.

   • C ≦10.

   • JOI 君が現在地から移動を開始して出口のマスで止まることができる場合は,必要な移動回数は10
   回以内である.



                    危険なスケート– 2 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                Contest Day 4 – Dangerous Skating


小課題2 [65 点]

 以下の条件を満たす.

   • R ≦200.

   • C ≦200.


小課題3 [22 点]

 追加の制限はない.


入出力例

  入力例1        出力例1
   5 5                  4
   #####
   #...#
   #...#
   #...#
   #####
   2 2
   3 3

 入力例1 において,スケートリンクの初期状態は以下の通りである.白の四角形が書かれたマスは氷塊
を,J と書かれたマスはJOI 君の現在地を,E と書かれたマスは出口を表す.


  □ □ □ □ □
  □    J      □
  □     E   □
  □        □

  □ □ □ □ □

 まず,JOI 君が東向きに移動すると,その後のスケートリンクの状態は以下のようになる.


  □ □ □ □ □
  □ □         J □
  □     E   □
  □        □

  □ □ □ □ □

 この後JOI 君が西向き,南向き,北向きの順に移動することで,合計4 回の移動で出口で止まることが
できる.3 回以下の移動で出口で止まることはできないので,4 を出力する.



                    危険なスケート– 3 / 4

Japanese Olympiad in Informatics 2015/2016
                                                         Spring Training Camp/Qualifying Trial
                                             March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                              Contest Day 4 – Dangerous Skating




 入力例2        出力例2
 8 6                  5
 ######
 #..#.#
 ##...#
 #....#
 #.#..#
 #....#
 ##...#
 ######
 4 3
 6 4


 入力例3        出力例3
 5 5                  -1
 #####
 #.#.#
 #.#.#
 #.#.#
 #####
 2 2
 4 4


 入力例4        出力例4
 3 3                  0
 ###
 #.#
 ###
 2 2
 2 2

入力例4 において,JOI 君の現在地は出口のマスであるから,必要な移動回数は0 回である.





                   危険なスケート– 4 / 4