「COCI 2021.1 Patkice II」题解 题目大意 给定一个 $r \times s$ 的网格地图，包含以下字符：

o：起点（鸭子从此出发，选择上下左右任一方向）

x：终点

< > v ^：箭头，强制鸭子向对应方向移动

.：陷阱（不能经过）

一次成功的旅游需要满足：

不经过陷阱 .

不越界

不回到起点

不陷入循环

最终到达终点 x

可以修改地图上的箭头（不能改起点和终点），求最少修改次数，并输出一种方案。

问题分析 这实际上是一个最短路问题：

每个格子是一个节点

从起点 o 的四个邻接点开始，沿着箭头走

如果当前格子箭头指向的方向与我们需要的不一致，就需要修改（代价 1）

目标：找到从起点邻域到终点的最小修改路径

核心思路 图论建模 把网格看作图：

节点：每个格子 $(i, j)$

边：

如果当前格子是箭头，自然出边到对应方向（代价 0，如果使用原方向）

也可以“修改”箭头，得到其他方向的出边（代价 1）

实际上，这是一个 0-1 BFS 问题：

沿着当前箭头方向走：代价 0

改变箭头方向走到其他方向：代价 1

算法步骤 从起点 o 的四个邻居开始 BFS

使用双端队列 deque：

如果沿着当前格子箭头方向走，push_front（代价 0）

如果改变方向走到其他方向，push_back（代价 1）

记录到达每个格子的最小代价

同时记录路径来源，用于输出方案

构造方案 从终点反向追踪到起点某个邻居，确定路径：

路径上的格子：如果箭头方向与路径方向一致，则不改；否则改为路径方向

非路径上的格子：保持原样

复杂度分析 节点数：$O(rs)$

每个节点最多 4 条出边

0-1 BFS 复杂度：$O(rs)$

满足 $r,s \le 2000$ 的限制

示例演示 样例 1：

text

vo vv> x>> BFS 发现最优路径需要改 1 处（终点上方格子从 > 改为 <）：

text

vo vv> x<> 实现细节 方向数组：int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

方向字符：char dirs[] = {'^', 'v', '<', '>'};

使用 deque 进行 0-1 BFS

记录 pre[i][j] 表示 $(i,j)$ 的前驱格子和方向

总结 本题的关键在于将修改箭头的问题转化为带权最短路问题，利用 0-1 BFS 高效求解。这种“状态空间搜索”是处理网格修改问题的常用技巧。

标签：图结构、搜索、最短路