题解

思路

一天内，船员的操作向量与风向量相加，终点相对起点的偏移只属于一个很小的固定集合。终点还必须在地图内、是海洋格子，并且与起点属于同一个四连通海洋分量。先用 BFS 标记全部海洋分量，之后可常数时间判断一次位移是否合法。

任何一天都能原地不动：有风时选择与风相反的操作，无风时直接停留。因此某格一旦可达，在食物允许的更晚日期仍可达。可把起点和至多 $T$ 个补给事件当作新的满食物出发源。

做法

子任务 1：逐日食物动态规划

记录每个格子在当天结束时最多还剩多少食物。枚举当天所有可达格子与五种操作，转移到下一天；到达当天营业的补给点时把剩余食物重置为 $K$。小范围内直接模拟全部 $W$ 天。

子任务 2：按补给事件逐源推进

起点对应时间 $0$，每个补给点对应营业时间 $F_i$。一个事件可达后，从该格、该时刻出发，用布尔网格推进至多 $K$ 天。若到达港口就更新答案；若在第 $F_j$ 天覆盖补给点 $j$，则把事件 $j$ 加入队列。每个事件只处理一次，显式枚举网格和五种操作。

满分做法：连通分量位移掩码

把 $NM$ 个格子按行展开为位集合。对每种风和每种操作预处理源格掩码：仅当偏移终点在地图内且与源格同属一个海洋分量时，该源格位为一。

若当前可达集合为 $R$，展开偏移为 $\Delta$，对应下一日集合为

$$(R\mathbin{\&}\text{allowed}_{wind,action})\ll\Delta.$$

负偏移改用右移。把五种操作的结果按位或即可得到下一日全部可达格，再沿用补给事件队列，每个源只推进 $K$ 天。

正确性证明

连通分量预处理准确刻画四连通海路。固定风和操作后，向量和唯一确定终点；源掩码同时检查边界、海洋属性和分量相等，所以一次掩码平移得到且只得到该操作的合法终点。对五种操作取并集，恰为下一天所有可能位置。

从一个满食物事件出发，逐日推进 $0$ 到 $K$ 天，枚举了食物耗尽前的所有航行方案。又因为每天能原地等待，逐日集合能准确判定固定营业日的补给是否可用。

起点事件显然可达。按事件时间归纳，每个入队补给都存在合法航线；反过来，合法航线的相邻两次补给间隔不超过 $K$ 天，处理前一事件时必会发现后一事件。因此算法发现且只发现所有可达补给，并检查了其食物范围内的全部港口到达时刻，最小值正确。

复杂度

小层时间复杂度为 $O(WNM)$，空间复杂度为 $O(NM)$。

中层时间复杂度为 $O((T+1)KNM)$，空间复杂度为 $O(NM)$。

满分令 $B=\lceil NM/64\rceil$，时间复杂度为 $O(NM+(T+1)KB)$，空间复杂度为 $O(B)$ 加固定数量的预处理掩码。