atcoder#ABC246E. [ABC246E] Bishop 2

[ABC246E] Bishop 2

题目描述

ここに、 N × N N\ \times\ N のチェス盤があります。このチェス盤の上から i i 行目、左から j j 列目にあるマスをマス (i,j) (i,j) と呼びます。
チェス盤の情報は N N 個の文字列 Si S_i として与えられます。
文字列 Si S_i j j 文字目である Si,j S_{i,j} には、以下の情報が含まれています。

  • Si,j= S_{i,j}= . のとき マス (i,j) (i,j) には何も置かれていない。
  • Si,j= S_{i,j}= # のとき マス (i,j) (i,j) には白のポーンが 1 1 つ置かれている。このポーンを動かしたり取り除いたりすることはできない。

この盤面のマス (Ax,Ay) (A_x,A_y) に、白のビショップを 1 1 つ置きました。
この白のビショップをチェスのルール (注記参照) に従ってマス (Ax,Ay) (A_x,A_y) からマス (Bx,By) (B_x,B_y) に移動させるために必要な最小の手数を求めてください。
ただし、移動できない場合は代わりに -1 を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N Ax A_x Ay A_y Bx B_x By B_y S1 S_1 S2 S_2 \vdots SN S_N

输出格式

答えを出力せよ。

题目大意

给定有障碍的网格图,. 为空地,# 为障碍。给定起点终点,每次移动仅可以斜向走任意长度,问从起点到终点的最少移动次数,可能无解,无解输出 -1

5
1 3
3 5
....#
...#.
.....
.#...
#....
3
4
3 2
4 2
....
....
....
....
-1
18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................
9

提示

注記

マス (i,j) (i,j) に置かれている白の ビショップ は、 1 1 手で以下のルールに従って移動することができます。

  • 各正整数 d d について、以下の条件を全て満たせばマス (i+d,j+d) (i+d,j+d) に移動できる。

    • マス (i+d,j+d) (i+d,j+d) が盤内に存在する
    • 全ての正整数 l  d l\ \le\ d について、 (i+l,j+l) (i+l,j+l) に白のポーンがない
  • 各正整数 d d について、以下の条件を全て満たせばマス (i+d,jd) (i+d,j-d) に移動できる。

    • マス (i+d,jd) (i+d,j-d) が盤内に存在する
    • 全ての正整数 l  d l\ \le\ d について、 (i+l,jl) (i+l,j-l) に白のポーンがない
  • 各正整数 d d について、以下の条件を全て満たせばマス (id,j+d) (i-d,j+d) に移動できる。

    • マス (id,j+d) (i-d,j+d) が盤内に存在する
    • 全ての正整数 l  d l\ \le\ d について、 (il,j+l) (i-l,j+l) に白のポーンがない
  • 各正整数 d d について、以下の条件を全て満たせばマス (id,jd) (i-d,j-d) に移動できる。

    • マス (id,jd) (i-d,j-d) が盤内に存在する
    • 全ての正整数 l  d l\ \le\ d について、 (il,jl) (i-l,j-l) に白のポーンがない

制約

  • 2  N  1500 2\ \le\ N\ \le\ 1500
  • 1  Ax,Ay  N 1\ \le\ A_x,A_y\ \le\ N
  • 1  Bx,By  N 1\ \le\ B_x,B_y\ \le\ N
  • (Ax,Ay)  (Bx,By) (A_x,A_y)\ \neq\ (B_x,B_y)
  • Si S_i . および # からなる N N 文字の文字列
  • SAx,Ay= S_{A_x,A_y}= .
  • SBx,By= S_{B_x,B_y}= .

Sample Explanation 1

以下のように移動させることで 3 3 手でビショップを (1,3) (1,3) から (3,5) (3,5) まで移動させることができます。 2 2 手以内でビショップを (1,3) (1,3) から (3,5) (3,5) まで移動させることはできません。 - $ (1,3)\ \rightarrow\ (2,2)\ \rightarrow\ (4,4)\ \rightarrow\ (3,5) $

Sample Explanation 2

どのようにビショップを動かしても (3,2) (3,2) から (4,2) (4,2) に移動させることはできません。