#8141. 网格行走 (path) 题解 审核通过

CPP 刷题王 2024-03-21 16:57:47 13

题目分析

1. 存储方式

这道题目唯一的难点就是怎么存储地图,于是,我就想到了用一维数组来代替二维数组,因为题目说 ,所以我们只需要定义一个大小为 的数组来存储就行了。

2. 判断边界

由于我们用了一维数组存储,所以我们只需要判断 与 是否超出地图边界即可,至于怎么判断,我们可以找到下一步要走到的地方是否为 或是否超过了 。

3. 遍历数组

题目要求我们求出最小的没有走过的数,因此我们必须得尽量地走数字小的路径。

我们只需要贪心一波,判断我们右面的最小值与下面的最小值,然后朝最小值更小的方向走。

我们可以画图:

这张图中,我们肯定是向下走,因为向右走就没有办法走到 了。

4. 核心代码

1. 递归写法

bool check(int now2) {
    int res = 2147483646;
    for (int j = now2 + m; j <= k; j += m) res = (res < a[j] ? res : a[j]);
    int res2 = 2147483646;
    for (int i = now2 + 1; (i - 1) % m != 0 && i <= k; i++) res2 = (res2 < a[i] ? res2 : a[i]);
    return res < res2;
}
void dfs(int now2) {
    b[a[now2]] = 1;
    if (now2 == k) {
        for (int i = 0; i <= k + 10; i++) {
            if (!b[i]) {
                printf("%d", i);
                return;
            }
        }
    }
    if (now2 + m <= k) {
        if (now2 % m != 0 && now2 + 1 <= k) {
            if (check(now2))
                dfs(now2 + m);
            else
                dfs(now2 + 1);
        } else
            dfs(now2 + m);
    } else
        dfs(now2 + 1);
}

2. 递推写法

bool check(int now2) {
    int res = 2147483646;
    for (int j = now2 + m; j <= k; j += m) res = (res < a[j] ? res : a[j]);
    int res2 = 2147483646;
    for (int i = now2 + 1; (i - 1) % m != 0 && i <= k; i++) res2 = (res2 < a[i] ? res2 : a[i]);
    return res < res2;
}
void fs(int now2) {
    while (now2 != k) {
        b[a[now2]] = 1;
        if (now2 + m <= k) {
            if (now2 % m != 0 && now2 + 1 <= k) {
                if (check(now2))
                    now2 += m;
                else
                    now2++;
            } else
                now2 += m;
        } else
            now2++;
        b[a[now2]] = 1;
    }
    for (int i = 0; i <= k + 10; i++) {
        if (!b[i]) {
            printf("%d", i);
            return;
        }
    }
}
{{ vote && vote.total.up }}