CF1753D The Beach

Sword_K · 2022-10-24 19:37:37 · 题解

要加一张床，无非是通过一些操作使得空格凑在一起，那可以想到一个 dp：f_{i,j} 表示把 (i,j) 这个格子变成空格子的最小代价。如果 (i,j) 初始为空，那么 f(i,j)=0；如果是障碍，那么 f(i,j)=+\infty；如果是床，那么需要通过操作挪床。两个操作的本质都是固定床的一端，移动另一端，所以 (i,j) 一定是挪动的一端，那转移就只有 3 种情况，分类讨论即可。

dp 顺序怎么办呢？容易发现这个 dp 相当于是一个最短路，直接以所有空格子为起点，跑多源 dij 即可。

答案就是 \min_{|x_1-x_2|+|y_1-y_2|=1}\{f_{x_1,y_1}+f_{x_2,y_2}\}。

直接实现就可以通过此题，但是有一个问题，这个题是要凑出两个空格子，而跑最短路的时候是跑的一个空格，那会不会出现最后的答案里，同一张床被操作两次的情况呢（显然是不合法的操作）？答案是否定的，因为一旦出现了这种情况，这张床周围至少有 2 个空格，那么最多只需要操作这张床一次就可以把两个空格挪到一起。即不合法的答案一定不优。