Background

As for the last story... please see https://www.luogu.com.cn/problem/P1373.

Little A and his friend uim venture into the rainforest again. Suddenly, a south wind blows, dark clouds surge from the southern horizon, lightning flashes and thunder rumbles. In an instant, a gale rises, the sky is shrouded in clouds, and soon bean-sized raindrops start to fall. A monster with a bull’s head and a horse’s face appears ahead, growling: “Heh, since you’ve come here, neither of you will leave alive!” Little A and his companion are shocked once again.

Problem Description

In a flash, a huge matrix of $H$ rows and $W$ columns appears on the ground. Each cell is either empty land . or an obstacle #.

They start at $(1, 1)$ and must escape to the exit at $(H, W)$. They can move one cell up, down, left, or right; each such move counts as one operation. They still have the magic potion from their last adventure. If they drink it in one go, they can instantly teleport by the relative vector $(D, R)$; that is, if their current position is $(x, y)$, the new position becomes $(x + D, y + R)$. This also counts as one operation, but they can use this operation at most once (they may also choose not to drink the potion).

This is a dangerous place. They want to know the minimum number of operations needed to get out. However, it might be impossible to escape; in that case, they can only await their fate.

Input Format

The first line contains four integers $H$, $W$, $D$, $R$, whose meanings are explained in the description.

The next $H$ lines each contain a string of length $W$, consisting only of . and #.

Output Format

Output a single integer representing the minimum number of operations needed to escape. If they cannot escape, output $-1$.

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

5

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

-1

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

21

Hint

Sample explanation 1.

$(1, 1) \to (1, 2) \to (1, 3) \to$ drink the magic potion $\to (3, 4) \to (3, 5) \to (3, 6)$.

Sample explanation 2.

Since there is only one bottle of magic potion, they cannot escape.

Sample explanation 3.

$D$ and $R$ can also be $0$ or negative.

Constraints and Notes.

• For $40\%$ of the testdata, $2 \le H, W \le 5$.
• For $70\%$ of the testdata, $2 \le H, W \le 100$.
• For $100\%$ of the testdata, $2 \le H, W \le 1000$, $|D| < H$, $|R| < W$.

Translated by ChatGPT 5