题目大意

有一个 $n \times m$ 的网格海滩，每个格子可能是：

• 半张日光浴床：L（左半）、R（右半）、U（上半）、D（下半），它们与相邻的另一个半张组成一张完整的床；
• 空地 .；
• 障碍物 #。

一次操作可以移动一张完整的床，操作有两种：

• 旋转：抓住床的一边将其旋转 $90^\circ$，一半留在原地，另一半转到相邻的空格，代价为 $p$；
• 平移：沿床的长边移动一格，代价为 $q$。

任何时候每张床占据两个相邻的空格。你可以进行多次操作，但不能同时移动多张床。
目标是为 Andrew 腾出两个相邻的空格用来放置他的床。求最小的总不适感代价；若不可能，输出 $-1$。

数据范围
$1 \le n, m \le 300\,000$，$1 \le n \cdot m \le 300\,000$，$1 \le p, q \le 10^9$。

题解

1. 棋盘染色与视角转换

对网格进行黑白棋盘染色（相邻格子颜色不同）。因为每张床总是占据两个相邻格子，所以必然占据一个黑格和一个白格。

关键转换：不看作移动床，而是看作移动空格。
床的一次操作对应一个空格沿着床的某条边“跳”到另一个格子，且空格始终不改变所在格子的颜色。
例如，一张水平床（L 在 $(i,j)$，R 在 $(i,j+1)$），如果绕左半 $(i,j)$ 旋转，右半会移动到 $(i-1,j)$ 或 $(i+1,j)$，要求该格为空。从空格的角度看：原先在 $(i-1,j)$ 的空格会移动到 $(i,j+1)$，同时 $(i-1,j)$ 被床占据。

最终需要两个相邻空格，它们必然一黑一白。问题变成：从初始的所有空格出发，每次通过操作某张床使空格移动（代价 $p$ 或 $q$），最终让两个相邻异色格子都变为空格的最小总代价。

2. 建图

我们将每个非障碍格子看作图的一个结点，并在它们之间连有向边，表示空格的一次可能移动。

对每一张初始的床，根据其类型添加边：

设床占据的两个格子为 $(x_1,y_1)$ 和 $(x_2,y_2)$（相邻且颜色不同）。用 $w = p$ 或 $q$ 表示操作代价。

• 水平床： 左 L 在 $(r,c)$，右 R 在 $(r,c+1)$。

  • 旋转（代价 $p$）：
    绕 L 旋转 $\to$ 空格从 $(r-1,c)$ 或 $(r+1,c)$ 移动到 $(r,c+1)$；
    绕 R 旋转 $\to$ 空格从 $(r-1,c+1)$ 或 $(r+1,c+1)$ 移动到 $(r,c)$。
  • 平移（代价 $q$）：
    向左平移（长边方向）$\to$ 空格从 $(r,c-1)$ 移动到 $(r,c+1)$；
    向右平移 $\to$ 空格从 $(r,c+2)$ 移动到 $(r,c)$。

• 垂直床： 上 U 在 $(r,c)$，下 D 在 $(r+1,c)$。

  • 旋转（代价 $p$）：
    绕 U 旋转 $\to$ 空格从 $(r,c-1)$ 或 $(r,c+1)$ 移动到 $(r+1,c)$；
    绕 D 旋转 $\to$ 空格从 $(r+1,c-1)$ 或 $(r+1,c+1)$ 移动到 $(r,c)$。
  • 平移（代价 $q$）：
    向上平移 $\to$ 空格从 $(r-1,c)$ 移动到 $(r+1,c)$；
    向下平移 $\to$ 空格从 $(r+2,c)$ 移动到 $(r,c)$。

以上所有移动的起点、终点必须在网格内且不是 #。这样构建出的有向图中，每一条边恰好对应某一特定床的一次操作。
可以证明：在最优方案中，每张床最多被操作一次，因此图上的任何路径自然满足每张床至多使用一次（床被使用后位置改变，不会再产生原图的其他边）。

3. 多源最短路（Dijkstra）

将所有初始空地 . 作为源点，距离设为 $0$；其他格子距离设为 $+\infty$。
在上述有向图上运行 Dijkstra 算法，得到每个格子 $(x,y)$ 的距离 $d[x][y]$，表示将该格子变为空地所需的最小不适感代价。

4. 计算答案

枚举所有相邻的格子对 $(u,v)$（上下左右相邻），如果它们颜色不同（棋盘染色），且 $d[u]$ 和 $d[v]$ 都不是 $+\infty$，则用 $d[u] + d[v]$ 更新答案。

若不存在任何满足条件的相邻对，输出 $-1$；否则输出最小总代价。

5. 复杂度分析

• 结点数：$N = n \cdot m \le 300\,000$。
• 边数：每张床最多添加 $6$ 条边，总边数 $O(N)$。
• Dijkstra 使用优先队列：$O(N \log N)$。
• 总复杂度：$O(n m \log (n m))$，足以通过。

参考代码框架（略，按照上述建图与 Dijkstra 实现即可）