JavaT 村的水收集距离最小化

javaT村庄由代表房屋、水井、空地和禁区的字符网格（分别为“H”、“W”、“.”和“N”）表示。任务是确定每栋房屋到达最近水井并返回所需的最短距离。

在这个 n*m 的村庄网格中，标记为“H”的房屋居民忙于任务，需要从标记为“W”的水井取水。目标是计算每栋房屋到达最近水井并返回所需的最短距离，考虑了在网格边界内向左、向右、向上和向下滑动的限制。

例如，如果村庄被布局成一个 3x3 的网格，“H”代表房屋，“W”代表水井，那么输出显示了每栋房屋到达最近水井并返回所需的最短距离。角落的房屋到水井的最小距离可能为 4 个单位，离角落不远的房屋到水井的距离为 2 个单位，或者角落的房屋到水井的距离为 1 个单位，返回的距离为 2 个单位。

在另一个场景中，考虑一个 5x5 的网格，其中包含房屋、禁区和水井，输出说明了每栋房屋需要旅行的最小距离。有些房屋可能由于周围的禁区（“N”）而无法获得任何水井，导致距离为 -1。其他房屋将遵循与前一个示例类似的策略来计算最小旅行距离。

挑战在于创建一个高效计算这些最小距离的算法，该算法考虑禁区，并确定每栋房屋在村庄网格内到达最近水井并返回的最短路径。

测试用例

测试用例 1

• 输入
• 网格大小：4x4
• 网格表示
  {{H, ., H, H},
  {H, W, H, H},
  {., H, ., H},
  {H, H, H, H}}
• 输出
  2 0 2 2
  0 0 2 2
  2 2 2 2
  2 2 2 2
• 说明
  • 在此场景中，“H”代表房屋，“W”代表水井，而“.”表示空地。
  • 输出显示了每栋房屋到达最近水井并返回所需的最短距离。
  • 靠近水井的房屋的最小距离为 2（1 个单位到水井，1 个单位返回）。与直接连接到水井的空地相邻的房屋的最小距离也为 2。
  • 其余房屋的最小距离为 0，因为它们已经靠近水井。

测试用例 2

• 输入
  • 网格大小：3x3
  • 网格表示
    {{H, N, H},
    {H, H, W},
    {., H, .}}
• 输出
  4 0 2
  2 2 0
  2 0 2
• 说明
  • 在此，“H”代表房屋，“W”代表水井，“.”表示空地，“N”表示禁区。
  • 输出显示了每栋房屋到达最近水井并返回所需的最短距离。
  • 角落的房屋的最小距离为 4（2 个单位到水井，2 个单位返回）。
  • 靠近水井的房屋的最小距离为 2（1 个单位到水井，1 个单位返回）。
  • 其余可以直接到达水井的房屋的最小距离为 0。

解决此问题所使用的算法

为了高效地解决这个问题，您可以使用广度优先搜索（BFS）算法的修改版本

1. 初始化
   • 创建一个距离矩阵，将所有等于网格大小的单元格初始化为最大值。
   • 创建一个队列来执行 BFS。
2. 识别水井
   • 找到网格中的所有水井并标记它们的位置。
3. 执行 BFS
   • 对于识别出的每个水井
     • 从水井的位置开始 BFS。
     • 探索相邻单元格（左、右、上、下），同时跟踪距离。
     • 使用从水井到每个单元格的最小距离更新距离矩阵。
     • 继续直到访问了所有从水井可达的单元格。
4. 计算房屋距离
   • 遍历网格中的每个房屋。
   • 对于每个房屋，使用第 3 步中创建的距离矩阵检查其到最近水井的距离。
   • 更新每栋房屋到达最近水井并返回的最小距离。
5. 处理禁区
   • 如果存在禁区（“N”），请确保在 BFS 遍历期间不考虑这些单元格。您可以通过将这些单元格标记为已访问或在计算距离时忽略它们来做到这一点。
6. 输出
   • 生成显示每栋房屋到达最近水井并返回所需最小距离的矩阵。

算法说明

• 该算法确保网格中的每个单元格在从每个水井进行的 BFS 遍历中最多被访问一次。
• 它考虑了限制移动的方向，并在计算距离时避开禁区。
• 使用 BFS 有助于高效地计算从水井到网格中所有可达单元格的最短距离。
• 创建距离矩阵后，使用预先计算的距离，从房屋到水井的距离计算将成为一个简单的查找过程。

输出

说明

函数：

1. shortest_distance_village() - 查找最短距离网格的主函数

参数

1. n - 网格的行数
2. m - 网格的列数
3. grid - 输入的二维网格

变量

1. res- 输出二维网格，用于存储最短距离
   • 所有单元格均初始化为 float('inf')
2. q- 用于维护 BFS 遍历顺序的队列
   • 使用 deque 实现
3. dx[] - 4 个邻居的 x 方向偏移量
4. dy[]- 4 个邻居的 y 方向偏移量
5. curx, cury- 当前单元格坐标
6. x, y- 邻居单元格坐标

工作方式

1. 从 collections 导入 deque。它将用作 BFS 遍历的队列。
2. 定义 shortest_distance_village() 函数，该函数将网格尺寸 n、m 以及网格本身作为参数。
3. 创建一个二维数组 res 来存储最终的最短距离。将所有单元格初始化为无穷大。
4. 创建一个 deque q 用作队列。
5. 遍历网格并查找所有“W”单元格。将它们的坐标放入 q 并将它们在 res 中的距离设置为 0。
6. 定义 dx 和 dy 数组以获取 4 个邻居偏移量。
7. 开始 BFS 遍历
   • 从 q 中弹出一个单元格并获取其 x,y 坐标
   • 使用偏移量检查 4 个邻居
   • 如果邻居有效、在边界内、不是“N”，并且其当前 res 值 > curr + 1
     • 将邻居附加到 q
     • 将其距离更新为 curr dist + 1
8. BFS 之后，填充 res
   • '.' 单元格的距离为 0
   • 'N' 单元格保持无穷大
   • 未到达的其他单元格为 -1
   • 将已到达单元格的距离乘以 2
9. 返回最短距离的 res 网格
10. 驱动代码定义了一个示例输入，调用了该函数，并打印了输出网格。

结论

在村庄网格中，关键是要尽可能有效地计算房屋到达邻近水井的最短路径。这些理想路线是使用 BFS 等算法找到的，该算法会考虑禁区和移动限制。通过有条理地计算这些行程，程序确保家庭能够以短距离到达水源，从而提高村庄的效率。