P17052 [NWERC 2022] 代尔夫特距离 / Delft Distance
题目背景
译自 [Northwestern Europe Regional Contest (NWERC) 2022](https://2022.nwerc.eu) Problem D。
原题许可协议为 CC BY-SA。
题目描述
你现在在代尔夫特西北角的一家酒店里，想去位于代尔夫特东南角大学里的比赛场地。要到那里，你必须穿过这座城市的历史中心。
像曼哈顿一样，这座城市由一个 $h\times w$ 的建筑网格组成。但与曼哈顿不同的是，城市里不仅有正方形住宅建筑，还有一些圆形的中世纪塔楼。所有正方形建筑都与坐标轴平行，边长为 $10~\text{m}$；所有圆形塔楼的直径都是 $10~\text{m}$。任意两个相邻建筑之间恰好有一条宽度可以忽略不计的小巷。
因为你已经快赶不上比赛开始了，所以你需要找到一条从酒店到比赛场地的最短路径。幸运的是，你有一张城市地图。
:::align{center}
:::
图：样例输入 1 的示意图，红色路径是一条最短路径。
输入格式
输入包含：
- 一行两个整数 $h$ 和 $w$（$1 \leq h,w \leq 700$），表示城市地图中建筑的行数和列数。
- 接下来 $h$ 行，每行包含 $w$ 个字符，每个字符要么是 `O`（表示圆形塔楼），要么是 `X`（表示正方形建筑），描述建筑的形状。
地图以北方朝上。
输出格式
输出从代尔夫特西北角到东南角的一条最短路径长度，单位为米。你的答案允许相对或绝对误差至多 $10^{-6}$。
说明/提示
【数据规模与约定】
对于所有数据，满足 $1 \leq h,w \leq 700$；地图字符只可能是 `O` 或 `X`；答案允许绝对或相对误差至多 $10^{-6}$。