CF413E Maze 2D

R2 公司在 2D 游戏领域的最新产品是一种革命性的新算法，用于在 $2×n$ 迷宫中搜索最短路径。 想象一个 $2×n$ 的迷宫，这个长方形被划分为若干个单元格。每个单元格要么为空单元格，要么为障碍。每次可以从一个空单元格移动到任意相邻（上下左右）且为空的单元格，每次移动耗时 1 单位时间。最短路径问题表述如下：已知两个空单元格，需要你求出其中一格到另一格的最短所需时间。 遗憾的是，开发出的算法虽然能很好地响应一次最短路径请求，但实际上此类请求非常频繁。作为 R2 的首席程序员，你需要优化算法，以高效响应多次最短路径查询。请你编写一个程序，高效处理多次在 $2×n$ 迷宫中查找最短路径的请求。

第一行为两个整数 $n$ 和 $m$，分别表示迷宫的宽度和查询次数（$1 \leq n \leq 2 \cdot 10^{5}$，$1 \leq m \leq 2 \cdot 10^{5}$）。接下来两行各有 $n$ 个字符，分别描述迷宫的两行。每个字符要么为 '.'（表示空单元格），要么为 'X'（表示障碍）。 接下来 $m$ 行，每行两个整数 $v_{i}$ 和 $u_{i}$（$1 \leq v_{i}, u_{i} \leq 2n$），描述第 $i$ 次查询。$v_{i}$、$u_{i}$ 表示需要计算从编号 $v_{i}$ 的单元格到编号 $u_{i}$ 的最短路径长度。迷宫第一行的单元格从左到右依次编号为 $1$ 到 $n$，第二行从左到右编号为 $n+1$ 到 $2n$。保证查询中的单元格均为开阔单元格。

输出共 $m$ 行。对于第 $i$ 次查询，输出一行：若能到达则输出最短路径长度，否则输出 $-1$。

由 ChatGPT 5 翻译