You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

逃离冰阵

题目背景

题目描述

小明在玩一个闯关游戏，他操控的勇者被冰之魔女困在了冰阵里。这个冰阵可以用一个$n*m$的矩形表示，冰之魔女为了困住勇者，在冰阵四周都放置了冰墙（即第$1$行，第$n$行，第$1$列，第$m$列都是冰墙）。

小明操控的勇者想要逃离冰阵，需要刚好停在精灵法师已经在冰阵中布好的传送阵上。但是由于冰面太滑，勇者只能在冰面上沿水平或者竖直方向滑行，直到冰墙的前面一格停下。但是当勇者停在一个格子时，冰之魔女会使用魔法让那个格子在勇者离开的一瞬间升起冰墙。注意勇者一开始停在的格子也计算在内。

小明有一次呼叫精灵法师支援的机会，但他不想浪费这个机会，所以他想知道勇者到底能否离开这个冰阵。同时由于勇者在冰阵里每滑一次都要消耗生命值，所以小明也想知道当勇者能离开冰阵时，需要滑的最少步数。

输入格式

第一行是两个正整数$n$和$m$。

后面$n$行每行$m$个字符表示冰阵。字符为'#'表示该格为冰墙不可通过，字母为'.'表示该格为冰面可以通过。

接下来一行两个正整数$x_0,y_0$表示勇者当前开始的坐标。

接下来一行两个正整数$x_1,y_1$表示传送阵所在坐标。

输出格式

一行一个整数表示结果，如果不能逃出冰阵输出-1，否则输出最小步数。注：如果起点和终点重合输出0。

样例 #1

样例输入 #1

5 5
#####
#...#
#...#
#...#
#####
2 2
3 4

样例输出 #1

3

提示

样例解释1：

可以这么滑：

(2,2)往下到(4,2)，往上到(3,2)，往右到(3,4)。

可以证明不存在比3步更少的滑法。

数据范围

对$15\%$的数据，有$n,m≤10$。

对$80\%$的数据，有$n,m≤200$。

对$100\%$的数据，有$3≤n,m≤1000,1≤x_0,x_1≤n,1≤y_0,y_1≤m$，保证$(x_0,y_0),(x_1,y_1)$两格都是冰面，且第$1$行，第$n$行，第$1$列，第$m$列都是冰墙。