模拟
本题聚焦于地图变换与连通块划分问题,目标是判断能否借助特定的行、列交换操作,将给定地图分割为两个或更多的连通块。
1. 存在行列均含障碍物的点的情形:若地图中存在某个点,其所在行与列均包含障碍物,处理过程相对简单。可以先将需要分隔的物品移动至地图的四个角落, 随后利用这些障碍物将物品包围起来,以此实现地图的分隔。
2. 不存在行列均含障碍物的点的情形:当不存在满足上述条件的点时,经推导可知,所有障碍点能够通过一定的移动,组合形成一个矩形。 在此情况下,核心任务转变为判断能否借助这个矩形,将地图中的空白点分割成两个或更多的连通块。
可以证明对于 1 情况,最多移动 4 次,对于 2 情况,最多移动 2 次。