### 问题描述 小怂和小乐是好朋友，他们一起去到雨林中探险，突然雷风大作，紧接着豆大的雨点从天空中打落下来，然后一只大怪物出现了，小怂与小乐惊呆了，吓得抱在了一起。 瞬间，地上出现了一个 $n$ 行 $m$ 列的超大矩阵，矩阵的每个格子要么是空地 `.` 或者是障碍 `#`。 他们的起点在 $(1, 1)$，要逃到 $(n, m)$ 的出口。他们可以上下左右移动一格，这样算作一步。但是幸运的是，他们手上有一个一次性传送门，使用传送门可以瞬移到相对自己位置的 $(D, R)$ 向量，也就是说假设他们原来在 $(x, y)$，使用传送门可以到 $(x + D, y + R)$，这个也算作一步。当然，他们也可以不使用传送门；$D, R$ 可以为负数或零。 他们都很害怕，想要赶紧逃离，所以他们想要知道最小需要几步操作可以离开这个地方，当然他们也可能逃不出来，那就只能等死。 ### 输入格式 第一行有 $4$ 个正整数， $n, m, D, R$，具体意义已经在问题描述说明。 接下来 $n$ 行，每行长度是 $m$，仅有 `.` 或者 `#` 的字符串。 数据保证：$1 \leq n, m \leq 1000$，$\left \lvert D \right \rvert < n$，$\left \lvert R \right \rvert < m$。 ### 输出格式 一行，一个整数，表示逃出这个地方的最小步数。如果他们逃不出来，则输出 $-1$。 ### 样例输入 $1$ ```plaintext 3 6 2 1 ...#.. ..##.. ..#... ``` ### 样例输出 $1$ ```plaintext 5 ``` ### 样例输入 $2$ ```plaintext 3 7 2 1 ..#..#. .##.##. .#..#.. ``` ### 样例输出 $2$ ```plaintext -1 ``` ### 样例解释 样例解释 $1$ $(1,1) \to (1,2) \to (1,3) \to$ 使用传送门 $\to (3,4) \to (3,5) \to (3,6)$。 样例解释 $2$ 只有一个一次性传送门的话，他们没办法逃出来。