背景

译自 Northwestern Europe Regional Contest (NWERC) 2022 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}$。

3 5
XOOXO
OXOXO
XXXXO

71.4159265359

1 4
XOOX

45.7079632679

提示

【数据规模与约定】

对于所有数据，满足 $1 \leq h,w \leq 700$；地图字符只可能是 O 或 X；答案允许绝对或相对误差至多 $10^{-6}$。