为了方便你构建 OJ 测试数据，我编写了以下数据生成器。它包含了标准的 0-1 BFS 算法（用于生成 .out 答案）以及覆盖各种边界和特殊情况的构造逻辑（用于生成 .in 输入）。

数据生成器设计策略 (10 个测试点)

1. Case 1 (最小边界)：$1 \times 1$ 矩阵。
2. Case 2 (小规模随机)：$2 \times 2$ 矩阵。
3. Case 3 (零代价路径)：$3 \times 3$ 矩阵，通过构造确保有一条不需修改的路径（对应样例 2）。
4. Case 4 (细长矩阵)：$1 \times 100$ 矩阵，测试水平移动逻辑。
5. Case 5 (极高矩阵)：$100 \times 1$ 矩阵，测试垂直移动逻辑。
6. Case 6 (全错位构造)：$100 \times 100$ 矩阵，所有箭头都指向左或上（2 或 4），强制进行大量修改。
7. Case 7 (蛇形路径)：$100 \times 100$ 矩阵，构造一条 0 代价的蛇形路径。
8. Case 8 (随机大规模)：$100 \times 100$ 随机矩阵，测试一般情况下的性能。
9. Case 9 (最大规模随机)：$100 \times 100$ 随机矩阵。
10. Case 10 (障碍群构造)：$100 \times 100$ 矩阵，中间部分全部指向远离终点的方向。

数据生成器代码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <string>
#include <random>
#include <ctime>
#include <algorithm>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

// --- 标程：0-1 BFS 算法用于生成 .out ---
int solve_std(int m, int n, const vector<vector<int>>& grid) {
    if (m == 1 && n == 1) return 0;
    
    int dr[] = {0, 0, 0, 1, -1};
    int dc[] = {0, 1, -1, 0, 0};
    vector<vector<int>> dist(m, vector<int>(n, INF));
    deque<pair<int, int>> dq;

    dist[0][0] = 0;
    dq.push_back({0, 0});

    while (!dq.empty()) {
        pair<int, int> curr = dq.front();
        dq.pop_front();
        int r = curr.first, c = curr.second;

        if (r == m - 1 && c == n - 1) return dist[r][c];

        for (int i = 1; i <= 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                int w = (grid[r][c] == i ? 0 : 1);
                if (dist[r][c] + w < dist[nr][nc]) {
                    dist[nr][nc] = dist[r][c] + w;
                    if (w == 0) dq.push_front({nr, nc});
                    else dq.push_back({nr, nc});
                }
            }
        }
    }
    return dist[m-1][n-1];
}

// --- 写入函数 ---
void write_case(int id, int m, int n, const vector<vector<int>>& grid) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    ofstream fout(in_name);
    fout << m << " " << n << "\n";
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            fout << grid[i][j] << (j == n - 1 ? "" : " ");
        }
        fout << "\n";
    }
    fout.close();

    ofstream fans(out_name);
    fans << solve_std(m, n, grid) << endl;
    fans.close();
    cout << "Test Case " << id << " generated (" << m << "x" << n << ")" << endl;
}

int main() {
    mt19937 rng(time(0));
    auto get_rand = [&](int l, int r) {
        return uniform_int_distribution<int>(l, r)(rng);
    };

    // Case 1: 1x1
    write_case(1, 1, 1, {{1}});

    // Case 2: 2x2 Random
    write_case(2, 2, 2, {{get_rand(1,4), get_rand(1,4)}, {get_rand(1,4), get_rand(1,4)}});

    // Case 3: Sample 2 (Cost 0)
    write_case(3, 3, 3, {{1, 1, 3}, {3, 2, 2}, {1, 1, 4}});

    // Case 4: Long Horizontal
    {
        vector<vector<int>> g(1, vector<int>(100));
        for(int i=0; i<100; i++) g[0][i] = get_rand(1,4);
        write_case(4, 1, 100, g);
    }

    // Case 5: Tall Vertical
    {
        vector<vector<int>> g(100, vector<int>(1));
        for(int i=0; i<100; i++) g[i][0] = get_rand(1,4);
        write_case(5, 100, 1, g);
    }

    // Case 6: All Wrong Way (Pointing Left/Up)
    {
        vector<vector<int>> g(100, vector<int>(100));
        for(int i=0; i<100; i++)
            for(int j=0; j<100; j++) g[i][j] = (get_rand(0,1) ? 2 : 4);
        write_case(6, 100, 100, g);
    }

    // Case 7: Snake Path (Cost 0)
    {
        vector<vector<int>> g(100, vector<int>(100, 1));
        for(int i=0; i<100; i++) {
            if(i % 2 == 0) {
                for(int j=0; j<99; j++) g[i][j] = 1; // Right
                g[i][99] = 3; // Down
            } else {
                for(int j=99; j>0; j--) g[i][j] = 2; // Left
                g[i][0] = 3; // Down
            }
        }
        write_case(7, 100, 100, g);
    }

    // Case 8 & 9: Random Large
    for(int id = 8; id <= 9; id++) {
        vector<vector<int>> g(100, vector<int>(100));
        for(int i=0; i<100; i++)
            for(int j=0; j<100; j++) g[i][j] = get_rand(1,4);
        write_case(id, 100, 100, g);
    }

    // Case 10: Anti-Optimal Cluster
    {
        vector<vector<int>> g(100, vector<int>(100));
        for(int i=0; i<100; i++)
            for(int j=0; j<100; j++) {
                if(i < 50 && j < 50) g[i][j] = (get_rand(0,1) ? 2 : 4); // Left/Up
                else g[i][j] = get_rand(1,4);
            }
        write_case(10, 100, 100, g);
    }

    return 0;
}

生成器设计要点：

1. 文件大小优化：
   • 最大规模为 $100 \times 100$，每个格子占约 2 字节（数字加空格）。
   • 单个 .in 文件约 20KB，10 个测试点总大小约 200KB，远低于 2MB 限制。
2. 区分算法复杂度：
   • 构造了蛇形路径（Case 7）和极长细窄矩阵（Case 4, 5），可以有效区分出那些在处理 0 权边时没有正确使用双端队列或优先队列导致重复搜索节点而超时的算法。
3. 时间效率与安全性：
   • 使用非递归的 0-1 BFS 作为标程，保证了生成 .out 文件时的绝对速度（全部 10 组数据生成仅需几十毫秒）。
   • 使用了 std::deque 和 pair，避开了复杂的递归逻辑，不存在爆栈风险。
4. 边界覆盖：
   • 包含了 $1 \times 1$ 的极小情况和 $100 \times 100$ 的最大规模，以及特定的方向诱导逻辑。

使用方法：

1. 编译并运行该代码：g++ -O3 gen.cpp -o gen && ./gen。
2. 当前目录下会生成 1.in, 1.out ... 10.in, 10.out。
3. 将这些文件打包上传到你的 OJ 系统即可。

在 NOI 竞赛中，此题是典型的最短路建模问题。虽然网格图中方向不断变化，但只要能抽象出“代价”即“边权”，问题就迎刃而解。

我们将从通用的 Dijkstra 算法 过渡到针对 0-1 边权的 0-1 BFS 算法。

版本一：Dijkstra 堆优化算法（通用满分方案）

思路分析： 我们将网格看作图：

1. 每个点 $(r, c)$ 到邻居有 4 条有向边。
2. 如果方向与 grid[r][c] 初始一致，则边权为 0。
3. 如果方向不一致（需要修改），则边权为 1。 由于边权非负，可以使用 Dijkstra 算法。

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

// 竞赛常数定义
const int INF = 0x3f3f3f3f;
const int MAXN = 105;

int m, n;
int grid[MAXN][MAXN];
int dist[MAXN][MAXN];

// 方向数组索引与题目 1, 2, 3, 4 一一对应
// 1: 右, 2: 左, 3: 下, 4: 上
int dr[] = {0, 0, 0, 1, -1};
int dc[] = {0, 1, -1, 0, 0};

struct Node {
    int r, c, d;
    // 堆优化：小根堆比较
    bool operator>(const Node& other) const {
        return d > other.d;
    }
};

void solve() {
    if (!(cin >> m >> n)) return;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> grid[i][j];

    // 初始化距离为无穷大
    memset(dist, 0x3f, sizeof(dist));
    dist[0][0] = 0;

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({0, 0, 0});

    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        int r = curr.r, c = curr.c, d = curr.d;

        // 剪枝：如果已经有更短的路径，跳过
        if (d > dist[r][c]) continue;
        if (r == m - 1 && c == n - 1) break;

        for (int i = 1; i <= 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                // 如果当前尝试的方向 i 等于 grid 原本的方向，代价为 0，否则为 1
                int weight = (grid[r][c] == i ? 0 : 1);
                if (dist[r][c] + weight < dist[nr][nc]) {
                    dist[nr][nc] = dist[r][c] + weight;
                    pq.push({nr, nc, dist[nr][nc]});
                }
            }
        }
    }
    cout << dist[m - 1][n - 1] << endl;
}

int main() {
    // 快速 IO，NOI 必备
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

• 时间复杂度：$O(MN \log(MN))$。对于 $100 \times 100$ 规模，约 $10^4 \times 13 \approx 1.3 \times 10^5$ 次运算。
• 空间复杂度：$O(MN)$。

版本二：0-1 BFS 算法（最优复杂度）

思路分析： 在图中，如果边权只有 0 和 1，Dijkstra 算法可以退化为 0-1 BFS。

• 逻辑：使用 deque（双端队列）。
• 如果松弛边的权值为 0，将节点插入 队首（优先处理）。
• 如果松弛边的权值为 1，将节点插入 队尾（延后处理）。 这样可以保证队列始终是关于距离单调递增的，从而省去了堆排序的 $O(\log N)$ 时间。

#include <iostream>
#include <deque>
#include <cstring>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int m, n;
int grid[MAXN][MAXN];
int dist[MAXN][MAXN];

int dr[] = {0, 0, 0, 1, -1};
int dc[] = {0, 1, -1, 0, 0};

void solve_01bfs() {
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> grid[i][j];

    memset(dist, 0x3f, sizeof(dist));
    dist[0][0] = 0;

    deque<pair<int, int>> dq;
    dq.push_back({0, 0});

    while (!dq.empty()) {
        pair<int, int> curr = dq.front();
        dq.pop_front();
        int r = curr.first, c = curr.second;

        if (r == m - 1 && c == n - 1) break;

        for (int i = 1; i <= 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                int w = (grid[r][c] == i ? 0 : 1);
                if (dist[r][c] + w < dist[nr][nc]) {
                    dist[nr][nc] = dist[r][c] + w;
                    // 0-1 BFS 核心：边权为 0 放队首，1 放队尾
                    if (w == 0) dq.push_front({nr, nc});
                    else dq.push_back({nr, nc});
                }
            }
        }
    }
    cout << dist[m - 1][n - 1] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve_01bfs();
    return 0;
}

• 时间复杂度：$O(MN)$。每个点只入队/出队常数次。
• 空间复杂度：$O(MN)$。

时间复杂度优化建议思考过程

1. Dijkstra 与 0-1 BFS 的取舍： 虽然 0-1 BFS 在理论上更快（少一个 $\log$），但在 $100 \times 100$ 这种小规模下，Dijkstra 的耗时通常在 1-5ms 之间，几乎无差别。在 NOI 赛场上，如果你对 deque 的 0-1 BFS 不太熟，直接写 Dijkstra 是最稳的选择。
2. 原地优化： 由于 $M, N$ 很小，可以考虑将坐标 (r, c) 压缩为 r * n + c 以减小结构体内存开销和 pair 的创建开销，但在本题规模下意义不大。
3. 常数优化： 使用 int 代替 struct 传参，或者使用链式前向星建图（如果边权更复杂的话），可以减少运行时间。

读题关键词与坑点总结

1. “最小代价”： 看到此词，第一反应应是“最短路”。
2. 方向映射关系： 1:右, 2:左, 3:下, 4:上。 易错点：写方向数组时一定要按此顺序排列，否则 grid[r][c] == i 的判断会全部出错。
3. “修改后终生有效”： 这意味着你不需要考虑“回头路”后方向又变回来的问题，这就是标准的单源最短路模型，而非动态规划或复杂的搜索。
4. 边界情况： 注意 $m=1, n=1$ 的情况，此时代价应为 0。代码逻辑中 while 循环起始即可处理。
5. 内存限制： $100 \times 100$ 的 int 数组只有 40KB 左右，远小于 256MB 的限制。

总结

对于这类网格图中带有“条件性移动”的题目，**“转换代价为边权”**是唯一的难点。一旦建图完成，本题就退化成了最基础的最短路模版题。在练习时，建议同时掌握 0-1 BFS 技巧，它是处理二进制权值图（如电路布线、有向网格修改）的利器。