← 返回题目列表

Codeforces · 413/E

E. 迷宫 2D

中文机器翻译题面 查看原题

R2公司在2D游戏领域的最后一个产品是一种在2×n迷宫中搜索最短路径的革命性新算法。

想象一个迷宫,看起来像一个 2 × n 矩形,分为单位正方形。每个单位方块要么是一个空单元格,要么是一个障碍物。在一个单位时间内,一个人可以从迷宫的一个空单元格移动到任何一侧相邻的空单元格。最短路径问题表述如下。给定两个自由迷宫单元,您需要确定从一个单元到达另一个单元所需的最短时间。

不幸的是,所开发的算法仅适用于寻找最短路径的一个请求,实际上此类请求经常发生。作为 R2 首席程序员,您受委托优化算法以找到最短路径。编写一个程序,该程序将有效地响应多个请求,以在 2 × n 迷宫中找到最短路径。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 2·105; 1 ≤ m ≤ 2·105) — 迷宫的宽度和查询的数量。接下来的两行包含迷宫。每行包含 n 个字符,每个字符等于“.” (空单元格)或“X”(障碍物)。

接下来的 m 行中的每一行都包含两个整数 vi 和 ui (1 ≤ vi, ui ≤ 2n) — 第 i 个请求的描述。数字vi、ui表示需要打印从迷宫编号vi的单元格到编号ui的单元格的最短路径的值。我们假设迷宫第一行的单元格从左到右编号为1到n,第二行的单元格从左到右编号为n+1到2n。保证两个给定的单元格都是空的。

输出

打印 m 行。在第 i 行中,打印第 i 个请求的答案 - 如果我们无法从第一个单元格到达第二个单元格,则打印最短路径的大小或 -1。

示例

输入 #1

4 7
.X..
...X
5 1
1 3
7 7
1 4
6 1
4 7
5 7

输出 #1

1
4
0
5
2
2
2

输入 #2

10 3
X...X..X..
..X...X..X
11 7
7 18
18 10

输出 #2

9
-1
3