【问题描述】

ROMA城中有一些古典的印度式建筑，这些建筑和周围的欧洲建筑风格格格不入。这些伪装成教堂的建筑其实是某国特工的基地。Tomas接受了一项任务，要求从某个教堂出发，逐个访问这些教堂，搞清楚每一个教堂的内部结构，并回到出发的地方。这些教堂很有规律地构成了一个 m × n 的矩形，每个教堂和它的八个方向的教堂有直接的路径相连。水平或垂直方向相邻的教堂之间的路程均为 1。请问Tomas至少需要走多远的路，才能完成这个危险而艰巨的任务呢？

【输入格式】

输入一行两个整数 m 和 n (m, n ≤ 10000) 表示矩阵的大小。

【输出格式】

输出一行一个实数，表示最少需要走的路程，保留两位小数。

【输入样例】

5 5

【输出样例】

8.00

【数据规模】

• 对于 10% 的数据：N ≤ 10^4, k ≤ 100
• 对于 10% 的数据：N ≤ 10^5, k ≤ 100
• 对于 10% 的数据：N ≤ 10^6, k = 1
• 对于前 60% 的数据：k < 1000
• 对于 100%的数据：1 ≤ k < 250000, k ≤ n < 10^7

【解题思路】

这道题是一个路径问题，涉及到图的遍历。题目要求计算最短路径，考虑到是一个矩形网格，可以使用 广度优先搜索 (BFS) 来计算每个教堂的最短距离。具体步骤如下：

1. ​输入矩阵的大小​：我们需要处理一个 m × n 的矩阵，每个格子代表一个教堂，起点为某个教堂。
2. ​**广度优先搜索 (BFS)**​：从起点开始，使用 BFS 算法逐步访问所有相邻的节点，直到遍历完所有的教堂。BFS 可以保证我们在最短的路径上访问每个节点。
3. ​最短路径计算​：由于每个教堂与其相邻的教堂的路径长度为 1，所以 BFS 能够直接计算出从起点到每个教堂的最短距离。
4. ​遍历所有节点​：根据题意，我们需要计算的是遍历所有教堂的最小路径长度。可以理解为求解一个 哈密尔顿回路 问题，起点到终点的路径即为最终的最短路径。

【优化考虑】

• 对于较大的 m 和 n，可以利用 并查集 或 动态规划 等方法优化搜索过程，减少复杂度。