小A和uim之大逃离 II

话说上回……还是参见 <https://www.luogu.com.cn/problem/P1373> 吧 小 a 和 uim 再次来到雨林中探险。突然一阵南风吹来，一片乌云从南部天边急涌过来，还伴着一道道闪电，一阵阵雷声。刹那间，狂风大作，乌云布满了天空，紧接着豆大的雨点从天空中打落下来，只见前方出现了一个牛头马面的怪物，低沉着声音说：“呵呵，既然你们来到这，两个都别活了！”。小 a 和他的小伙伴再次惊呆了！

瞬间，地面上出现了一个 $H$ 行 $W$ 列的巨幅矩阵，矩阵的每个格子上要么是空地 `.` 或者障碍 `#`。 他们起点在 $(1,1)$，要逃往 $(H,W)$ 的出口。他们可以一次向上下左右移动一格，这个算一步操作。不过他们还保留着上次冒险时收集的魔液，一口气喝掉后可以瞬移到相对自己位置的 $(D,R)$ 向量；也就是说，原来的位置是 $(x,y)$，然后新的位置是 $(x+D,y+R)$，这个也算一步操作，不过他们仅能至多进行一次这种操作（当然可以不喝魔液）。 这个地方是个是非之地。所以他们希望知道最小能有几步操作可以离开这个鬼地方。不过他们可能逃不出这个鬼地方，遇到这种情况，只能等死，别无他法。

第一行个整数，$H,W,D,R$，意义在描述已经说明。 接下来 $H$ 行，每行长度是 $W$，仅有 `.` 或者 `#` 的字符串。

请输出一个整数表示最小的逃出操作次数。如果他们逃不出来，就输出 $-1$。

3 6 2 1
...#..
..##..
..#...

5

3 7 2 1
..#..#.
.##.##.
.#..#..

-1

6 6 -2 0
.#....
.#.#..
.####.
.#..#.
.##.#.
....#.

21

样例解释 $1$ $(1,1) \to (1,2)\to (1,3)\to$ 喝魔液 $\to (3,4)\to (3,5)\to (3,6)$。 样例解释 $2$ 因为只有一瓶魔液所以他们没办法逃出来。 样例解释 $3$ $D$ 和 $R$ 还可以是 $0$或者负数。 数据范围与约定 $40\%$ 的测试数据 $2\leq H,W\leq 5$。 $70\%$ 的测试数据 $2\leq H,W\leq 100$。 $100\%$ 的测试数据 $2\leq H,W\leq 1000,|D|<H,|R|<W$。