题目解析

这道题的核心是在一个n×n的网格地图中，通过放置炸弹清除砖墙，寻找从起点到终点的最短路径。炸弹会清除与它在同一行或同一列的所有砖墙，前提是炸弹与这些砖墙之间没有坚固岩石阻挡。

算法思路

1. 基础思路

如果不放置炸弹，只需在原始地图上进行BFS搜索（将砖墙视为障碍物）即可。但放置炸弹后，地图的可通行性会发生变化，相当于可以选择一个格子，将其所在行和列上的砖墙（不被岩石阻挡的部分）全部清除。

直接枚举所有可能的炸弹放置位置并分别进行BFS，时间复杂度为O(n³)，对于n≤1000不可行。

2. 关键观察

• 炸弹的效果是清除整行和整列的砖墙（不被岩石阻挡）
• 放置炸弹后，从起点到终点的最短路径可以分解为：
  1. 从起点到炸弹所在行或列的某个格子
  2. 沿着炸弹所在行或列移动到另一个格子
  3. 从该格子到终点

3. 算法框架

1. 预处理距离：

   • 从起点P开始BFS，计算到每个空地和砖墙格子的最短距离（不考虑炸弹）
   • 从终点K开始BFS，计算到每个空地和砖墙格子的最短距离（不考虑炸弹）

2. 考虑炸弹效果：

   • 炸弹会清除整行整列的砖墙，这意味着在炸弹所在行或列上，可以"免费"移动（只要不被岩石阻挡）
   • 通过动态规划，计算从起点到每个格子，如果允许在行上"免费"移动的最短距离
   • 同样，计算从起点到每个格子，如果允许在列上"免费"移动的最短距离
   • 对终点也进行类似计算

3. 寻找最佳炸弹位置：

   • 遍历所有格子作为候选炸弹位置
   • 对于每个位置(i,j)，计算： min(从起点到(i,j)的行最短距离, 从起点到(i,j)的列最短距离) + min(从(i,j)到终点的行最短距离, 从(i,j)到终点的列最短距离)
   • 取最小值对应的位置为最佳炸弹位置

4. 路径重建：

   • 根据选择的最短路径方式（走行还是走列），使用保存的前驱信息重建路径

时间复杂度

• BFS：O(n²)
• 动态规划预处理：O(n²)
• 寻找最佳位置：O(n²)
• 总时间复杂度：O(n²)，可以处理n≤1000的数据

算法正确性证明

算法的正确性基于以下关键点：

1. 炸弹清除整行整列的效果等价于允许在炸弹所在行和列上"免费"移动（只要没有岩石阻挡）
2. 任何使用炸弹的最短路径都可以分解为：起点→炸弹行/列→炸弹位置→炸弹行/列→终点
3. 通过预处理四个距离数组（起点行、起点列、终点行、终点列），可以快速计算通过任意炸弹位置的最短路径

特殊情况处理

• 如果起点和终点在原始地图上就不连通，直接输出"NIE"
• 如果最佳路径长度超过3n²（初始化的极大值），说明没有可行方案，输出"NIE"

这个算法巧妙地利用了炸弹效果的特殊性，将三维的枚举问题（炸弹位置×路径搜索）降为二维的预处理问题，是典型的通过预处理优化复杂度的技巧。