使网格图中至少有一条有效路径的最小代价

题目描述

在一个 $m \times n$ 的网格图 grid 中，每个单元格都有一个初始的指示箭头，表示你位于该单元格时应当移动到的相邻单元格。

grid[i][j] 的值及其代表的方向：

• 1：向右移动（至 grid[i][j + 1]）
• 2：向左移动（至 grid[i][j - 1]）
• 3：向下移动（至 grid[i + 1][j]）
• 4：向上移动（至 grid[i - 1][j]）

箭头可能指向网格外部。你最开始位于左上角单元格 $(0, 0)$。一条 有效路径 是指从起点出发，沿着箭头方向移动，最终到达右下角单元格 $(m - 1, n - 1)$ 的序列。

在移动过程中，你可以花费 1 单位代价 修改任意单元格中的箭头方向。你可以将箭头改为四个方向中的任意一个，且修改后的方向永久生效。

请计算：使网格图中至少存在一条能够从起点到达终点的有效路径，所需的最小代价。

---

输入格式

第一行包含两个整数 $m$ 和 $n$，表示网格的行数和列数。 接下来 $m$ 行，每行包含 $n$ 个以空格分隔的整数，表示 grid[i][j] 的初始方向值。

输出格式

输出一个整数，表示所需的最小总代价。

---

输入输出样例

样例 1 (示例 1)

输入：

4 4
1 1 1 1
2 2 2 2
1 1 1 1
2 2 2 2

输出：

3

样例 2 (示例 2)

输入：

3 3
1 1 3
3 2 2
1 1 4

输出：

0

样例 3 (示例 3)

输入：

2 2
1 2
4 3

输出：

1

样例 4 (示例 4)

输入：

2 3
2 2 2
2 2 2

输出：

3

样例 5 (示例 5)

输入：

1 1
4

输出：

0

---

1. 预备知识点

• 单源最短路 (SSSP)：将修改代价抽象为边权，求解起点到终点的最小代价。
• 0-1 广度优先搜索 (0-1 BFS)：处理图中边权仅为 0 和 1 的特殊最短路算法，效率优于优先队列 Dijkstra。
• 双端队列 (std::deque)：0-1 BFS 的核心。当边权为 0 时，将新状态插入队首；边权为 1 时，插入队尾。
• 图论建模：将网格每个单元格视为节点，原本指向的方向边权为 0，其他方向边权为 1。

---

2. 启发式思路引导（草稿纸推理）

第一步：路径分析

我们站在格子 (r, c)。

• 如果我们顺着 grid(r, c) 指向的方向走，不花钱（代价为 0）。
• 如果我们想往其他三个方向走，必须花钱修改箭头（代价为 1）。

第二步：建模抽象

• 节点：网格中的每个坐标 $(r, c)$。
• 边：每个节点向上下左右四个邻居连边。
• 权值：
  • 若邻居的方向与当前格子箭头方向一致，边权 $w = 0$。
  • 若邻居的方向与当前格子箭头方向不一致，边权 $w = 1$。

第三步：算法选择

• 这是一个典型的最短路问题。
• 由于边权只有 0 和 1，我们可以使用 0-1 BFS。
• 0-1 BFS 保证了：从队首弹出的节点，其 dist 一定是当前已知的最小值，且队列中的 dist 保持单调递增（由于新增加的权值只有 0 或 1）。

第四步：复杂度思考

• 节点数 $V = M \times N = 100 \times 100 = 10,000$。
• 边数 $E \approx 4V = 40,000$。
• 0-1 BFS 复杂度 $O(V+E)$，约为 $5 \times 10^4$ 次操作，在 NOI 1s 时限内极速运行。

---

3. 算法逻辑流程图 (Mermaid)

graph TD
    A["开始: 初始化距离矩阵 dist 全部为无穷大"] --> B["设置 dist(0,0) 等于 0, 将坐标加入双端队列 DQ"]
    B --> C{"DQ 是否为空?"}
    C -- "是" --> D["输出最终结果 dist(m-1,n-1)"]
    C -- "否" --> E["从 DQ 队首取出当前点 (r, c)"]
    E --> F["循环 4 个方向 dir 等于 1,2,3,4"]
    F --> G["计算新坐标 (nr, nc)"]
    G --> H{"(nr, nc) 是否在界内?"}
    H -- "否" --> F
    H -- "是" --> I["判断代价 w: 若初始方向 grid(r,c) 等于 dir 则 w 等于 0, 否则 w 等于 1"]
    I --> J{"dist(r,c) 加 w 是否小于当前的 dist(nr,nc)?"}
    J -- "否" --> F
    J -- "是" --> K["更新 dist(nr,nc) 等于 dist(r,c) 加 w"]
    K --> L{"w 是否等于 0?"}
    L -- "是" --> M["将新坐标 (nr, nc) 插入 DQ 队首"]
    L -- "否" --> N["将新坐标 (nr, nc) 插入 DQ 队尾"]
    M --> F
    N --> F
    F -- "遍历完所有方向" --> C

---

4. 读题关键词与坑点总结

1. “最小代价”：最短路算法的核心关键词。
2. “1, 2, 3, 4 对应方向”：
   • 在定义方向数组时，务必与题目顺序一致。
   • 建议定义：int dr[] = {0, 0, 0, 1, -1}; int dc[] = {0, 1, -1, 0, 0};。
   • 这样 dr[grid[i][j]] 就能直接取出对应的坐标偏移。
3. “0-1 权值”：看到权值只有 0 和 1 且求最短路，一定要反映出 0-1 BFS (Deque)。
4. “终点到达”：$N=1$ 或 $M=1$ 的边界情况，Dijkstra 或 0-1 BFS 均能自然处理。
5. 空间限制：$100 \times 100$ 的 int 矩阵仅占用约 40KB，完全不必担心内存溢出。

5. 时间复杂度优化建议

• 对于 $100 \times 100$ 级别，std::deque 性能极佳。
• 如果在更大型的题目（如 $2000 \times 2000$）中，可以使用手写双端队列（用数组模拟指针）来进一步提升常数效率。
• 在松弛操作时，如果 dist[nr][nc] 已经被更新过且新路径不优，直接跳过。