问题分析

这是一个滑冰模拟+BFS求最短路问题。特殊规则在于：

1. 移动方式：向一个方向滑动，直到遇到冰块才停下
2. 冰块生成：每次蹬冰后，起点格子会变成冰块
3. 目标：停在出口位置（不能滑过）

关键观察

1. 移动特性

一次移动不是走到相邻格子，而是沿直线滑行到障碍物前：

• 从当前位置 $(r,c)$ 向某个方向移动
• 会一直滑行，直到下一个格子是冰块
• 停在最后一个非冰块格子

2. 状态变化

每次移动后，起点格子变成冰块，这会影响后续移动：

• 不能再回到这个格子
• 可能阻塞某些路径

3. 问题转化

可以看作在动态变化的网格上求最短路径：

• 网格状态随着移动而改变
• 需要记录每个格子的访问状态

算法选择：BFS

由于要求最少移动次数，自然想到BFS。但需要处理动态障碍物。

BFS状态设计

每个BFS状态包含：

• 当前位置 $(r,c)$
• 当前移动步数

难点：状态空间太大

直接BFS会超时，因为：

• $R,C \leq 1000$，网格有 $10^6$ 格子
• 每个格子可能被多次访问（因为冰块动态生成）

优化策略

1. 预处理滑动终点

对于每个格子 $(r,c)$，预处理四个方向能滑到的终点：这样在BFS中可以直接O(1)得到滑动终点。

2. 冰块生成的处理

当从 $(r,c)$ 滑动后，该格子变成冰块。这会影响：

• 其他路径不能再使用这个格子作为起点
• 但已经计算好的滑动终点仍然有效（因为滑动是从起点开始的）

实际上，一旦访问过某个格子，就可以标记为"已访问"，不再作为BFS的起点。

滑动终点计算

预处理滑动终点数组：

复杂度分析

• 预处理：$O(R \times C)$，每个格子处理4个方向
• BFS：每个格子最多访问一次，$O(R \times C)$
• 总复杂度：$O(R \times C)$，对于 $R,C \leq 1000$ 可接受

边界情况处理

1. 起点就是终点：直接返回0（样例4）
2. 无法到达：BFS结束后仍未到达终点，返回-1（样例3）
3. 四周都是冰块：题目已保证，不需要特殊处理

实现细节

1. 坐标处理：注意行列索引从1开始还是0开始
2. 冰块判断：移动前检查起点不是冰块，移动后起点变成冰块
3. 滑动终点：确保停在冰块前的最后一个非冰块格子

样例分析

样例1

5 5
#####
#...#
#...#
#...#
#####
2 2
3 3

路径：$(2,2) \rightarrow (2,3) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (3,3)$ 需要4步，因为每次移动后起点变成冰块，需要绕路。

总结

这道题的关键在于：

1. 理解滑动移动规则：不是单步移动，而是直线滑行
2. 处理动态障碍物：移动后起点变成冰块
3. 优化BFS：预处理滑动终点，避免重复计算
4. 正确建模：将问题转化为在动态网格上的最短路径问题

通过预处理+标准BFS，可以在 $O(RC)$ 时间内解决问题。