17713번 - 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 君の現在地はマス (r₁, c₁) である.このスケートリンクから脱出するには,出口のマス (r₂, c₂) で止ま る必要がある.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 行には,整数 r₁, c₁ が空白を区切りとして書かれている.これは,JOI 君の現在地がマス (r₁, c₁) であることを表す.
• 続く 1 行には,整数 r₂, c₂ が空白を区切りとして書かれている.これは,スケートリンクの出口がマ ス (r₂, c₂) であることを表す.

출력

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

제한

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

서브태스크 1 (13점)

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

서브태스크 2 (65점)

• R ≦ 200.
• C ≦ 200.

서브태스크 3 (22점)

追加の制限はない.

힌트