/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は魚屋にウナギを買いに行こうとしています。
高橋君の住む町は縦 H マス横 W マスからなるグリッド状の区画に分かれており、
各区画は道か壁かのいずれかです。
以下、上から i 番目 (1\leq i \leq H) かつ左から j 番目 (1\leq j\leq W) の区画を区画 (i,j) で表します。
各区画の情報は H 個の長さ W の文字列 S_1,S_2,\ldots,S_H で与えられ、
具体的には S_i の j 文字目 (1\leq i \leq H,1\leq j\leq W) が . のとき区画 (i,j) が道であることを、
S_i の j 文字目が # のとき区画 (i,j) が壁であることを表します。
高橋君は次の 2 種類の行動を好きな順番で繰り返し行うことができます。
- 上下左右に隣接する、町の中の区画であって、道であるようなものに移動する。
- 上下左右の方向を一つ決め、その方向に前蹴りを行う。
高橋君が前蹴りを行うと、現在いる区画からその方向に 1 つ前の区画および 2 つ前の区画について、その区画が壁ならば道に変えることができる。
ここで、1 つ前の区画または 2 つ前の区画が町の外である場合でも前蹴りを行うことができるが、町の外が変化することはない。
高橋君は最初、区画 (A,B) におり、区画 (C,D) にある魚屋まで移動したいです。
ここで、高橋君の最初にいる区画および魚屋のある区画は道であることが保証されます。
高橋君が魚屋にたどり着くために必要な 前蹴りの回数 の最小値を求めてください。
制約
- 1\leq H\leq 1000
- 1\leq W\leq 1000
- S_i は
.,#のみからなる長さ W の文字列 - 1\leq A,C\leq H
- 1\leq B,D\leq W
- (A,B)\neq (C,D)
- H,W,A,B,C,D は整数
- 高橋君の最初にいる区画および魚屋のある区画は道である。
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H A B C D
出力
高橋君が魚屋にたどり着くために必要な 前蹴りの回数 の最小値を出力せよ。
入力例 1
10 10 .......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. .##.#.#.#. ###.#.#.#. ###.#.#.#. #.....#... 1 1 7 1
出力例 1
1
高橋君は最初、区画 (1,1) にいます。
道である区画への移動を繰り返して区画 (7,4) まで移動することができます。
区画 (7,4) において左方向に対して前蹴りを行うと区画 (7,3) と区画 (7,2) が壁から道に変わります。
その後、道である区画（道に変わった区画を含む）への移動を繰り返して、区画 (7,1) にある魚屋に移動することができます。
このとき、前蹴りを行った回数は 1 回であり、前蹴りを行わずに魚屋へ移動することは不可能なため、1 を出力します。
入力例 2
2 2 .# #. 1 1 2 2
出力例 2
1
高橋君は最初、区画 (1,1) にいます。
右方向に対して前蹴りを行うと、区画 (1,2) を壁から道に変えることができます。
区画 (1,1) から右方向に 2 つ前のマスは町の外であるため、変化しません。
その後、高橋君は区画 (1,2) へ移動し、区画 (2,2) にある魚屋へ移動することができます。
このとき、前蹴りを行った回数は 1 回であり、前蹴りを行わずに魚屋へ移動することは不可能なため、1 を出力します。
入力例 3
1 3 .#. 1 1 1 3
出力例 3
1
前蹴りを行う際、それにより道に変えられ得る区画の中に魚屋のある区画が含まれていても問題ありません。 具体的には魚屋のある区画はもともと道であるため変化せず、特に前蹴りによって魚屋が壊れることはありません。
入力例 4
20 20 #################### ##...##....###...### #.....#.....#.....## #..#..#..#..#..#..## #..#..#....##..##### #.....#.....#..##### #.....#..#..#..#..## #..#..#.....#.....## #..#..#....###...### #################### #################### ##..#..##...###...## ##..#..#.....#.....# ##..#..#..#..#..#..# ##..#..#..#..#..#..# ##.....#..#..#..#..# ###....#..#..#..#..# #####..#.....#.....# #####..##...###...## #################### 3 3 18 18
出力例 4
3
Score : 400 points
Problem Statement
Takahashi is about to go buy eel at a fish shop.
The town where he lives is divided into a grid of H rows and W columns. Each cell is either a road or a wall.
Let us denote the cell at the i-th row from the top (1\leq i \leq H) and the j-th column from the left (1\leq j \leq W) as cell (i,j).
Information about each cell is given by H strings S_1,S_2,\ldots,S_H, each of length W. Specifically, if the j-th character of S_i (1\leq i \leq H,1\leq j\leq W) is ., cell (i,j) is a road; if it is #, cell (i,j) is a wall.
He can repeatedly perform the following two types of actions in any order:
- Move to an adjacent cell (up, down, left, or right) that is within the town and is a road.
- Choose one of the four directions (up, down, left, or right) and perform a front kick in that direction.
When he performs a front kick, for each of the cells at most 2 steps away in that direction from the cell he is currently in, if that cell is a wall, it becomes a road.
If some of the cells at most 2 steps away are outside the town, a front kick can still be performed, but anything outside the town does not change.
He starts in cell (A,B), and he wants to move to the fish shop in cell (C,D).
It is guaranteed that both the cell where he starts and the cell with the fish shop are roads.
Find the minimum number of front kicks he needs in order to reach the fish shop.
Constraints
- 1\leq H\leq 1000
- 1\leq W\leq 1000
- Each S_i is a string of length W consisting of
.and#. - 1\leq A,C\leq H
- 1\leq B,D\leq W
- (A,B)\neq (C,D)
- H, W, A, B, C, and D are integers.
- The cell where Takahashi starts and the cell with the fish shop are roads.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H A B C D
Output
Print the minimum number of front kicks needed for Takahashi to reach the fish shop.
Sample Input 1
10 10 .......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. .##.#.#.#. ###.#.#.#. ###.#.#.#. #.....#... 1 1 7 1
Sample Output 1
1
Takahashi starts in cell (1,1).
By repeatedly moving to adjacent road cells, he can reach cell (7,4).
If he performs a front kick to the left from cell (7,4), cells (7,3) and (7,2) turn from walls to roads.
Then, by continuing to move through road cells (including those that have become roads), he can reach the fish shop in cell (7,1).
In this case, the number of front kicks performed is 1, and it is impossible to reach the fish shop without performing any front kicks, so print 1.
Sample Input 2
2 2 .# #. 1 1 2 2
Sample Output 2
1
Takahashi starts in cell (1,1).
When he performs a front kick to the right, cell (1,2) turns from a wall to a road.
The cell two steps to the right of (1,1) is outside the town, so it does not change.
Then, he can move to cell (1,2) and then to the fish shop in cell (2,2).
In this case, the number of front kicks performed is 1, and it is impossible to reach the fish shop without performing any front kicks, so print 1.
Sample Input 3
1 3 .#. 1 1 1 3
Sample Output 3
1
When performing a front kick, it is fine if the fish shop’s cell is within the cells that could be turned into a road. Specifically, the fish shop’s cell is a road from the beginning, so it remains unchanged; particularly, the shop is not destroyed by the front kick.
Sample Input 4
20 20 #################### ##...##....###...### #.....#.....#.....## #..#..#..#..#..#..## #..#..#....##..##### #.....#.....#..##### #.....#..#..#..#..## #..#..#.....#.....## #..#..#....###...### #################### #################### ##..#..##...###...## ##..#..#.....#.....# ##..#..#..#..#..#..# ##..#..#..#..#..#..# ##.....#..#..#..#..# ###....#..#..#..#..# #####..#.....#.....# #####..##...###...## #################### 3 3 18 18
Sample Output 4
3