2 条题解

  • 5
    @ 2022-8-9 11:38:35

    好不容易啊……终于有一个带代码的题解了……(能给个顶吗

    UPD 8.9 11.44 修改了一下错误的格式,写上了代码用时,修复若干小问题。


    分析: 每个点都有一个高度,而要我们求符合要求的路线中,高度值最高与最低的值的差最小。一般求最大-最小的题都可以用二分差值。于是马上得出一个复杂度略(很)高的解法:

    1. 二分最大-最小
    2. 枚举最小,算出最大
    3. dfs 验证算出的范围是否能完成任务(将范围外的点删去)

    估算时间复杂度:O(log106×106×5050)O(log 10^6 \times 10^6 \times 5050)

    (log 1e6) 二分

    1e6 枚举下界

    5050 dfs

    优化一: 海拔值只有2500种,意味着我们只需要枚举下界2500次,即离散化。有多种方式,但为了简单并且方便,可以用STL的set/sort。

    优化二: 由于房子你必须经过,所以枚举下界和上界时下界小于等于房子的最小值,上界大于等于房子的最大值。(最强力的剪枝,直接快了1s左右)

    优化三: 其实这个有点卡数据,dfs使用时枚举方向的数组顺序要找好,不同顺序用时不同。

    优化四: dfs时判断点能不能走,用vis标记,在函数外预处理,可以搞进300ms。

    配合代码:

    #include <bits/stdc++.h>
    using namespace std;
    int n, sx, sy;
    char s[55][55];
    int h[55][55], vis[55][55], tim, sb[2505];
    int tx[2505], ty[2505], cnt;
    int dir[8][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}};
    int ans = 0x3f3f3f3f;
    
    void dfs(int x, int y, int l, int r) // dfs
    {
        if (vis[x][y] == tim || h[x][y] < l || h[x][y] > r) return; // 剪枝
        vis[x][y] = tim;
        for (int i = 0, u, v; i < 8; i++) // 枚举八个方向
            if ((u = dir[i][0] + x) >= 0 && u<=n && (v = dir[i][1] + y) >= 0 && v <= n) // 符合条件
                dfs(u, v, l, r); // dfs
    }
     
    bool chk(int d, int u) // check
    {
        tim++;
        dfs(sx, sy, d, u); // dfs
        for (int i = 0; i < cnt; i++)
            if (vis[tx[i]][ty[i]] != tim)
                return false;
        return true; // 只有所有的 vis[tx[i]][ty[i]] == tim 时才返回 true
    }
     
    int main()
    {
        // 输入
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%s", s[i]);
            for(int j = 0; j < n; j++)
                if (s[i][j] == 'P')
                    sx = i, sy = j; // 设置出发点
                else if (s[i][j] == 'K')
                    tx[cnt] = i, ty[cnt++] = j; // 设置目标点
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &h[i][j]), sb[++sb[0]] = h[i][j]; // 输入高度
        sort(sb + 1, sb + sb[0] + 1); // 排序
        sb[0] = unique(sb + 1, sb + sb[0] + 1) - sb - 1; // 去重,修改长度
        // 核心
        for (int i = 1, j = 0; i <= sb[0]; i++)
            for (; j + 1 <= sb[0] && chk(sb[j + 1], sb[i]); j++)
                ans = min(ans, sb[i] - sb[j + 1]);
        printf("%d\n", ans);
        return 0;
    } // 终于结束了
    

    AC版:(这才是最想要的

    #include <bits/stdc++.h>
    using namespace std;
    int n, sx, sy;
    char s[55][55];
    int h[55][55], vis[55][55], tim, sb[2505];
    int tx[2505], ty[2505], cnt;
    int dir[8][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}};
    int ans = 0x3f3f3f3f;
    
    void dfs(int x, int y, int l, int r)
    {
        if (vis[x][y] == tim || h[x][y] < l || h[x][y] > r) return;
        vis[x][y] = tim;
        for (int i = 0, u, v; i < 8; i++)
            if ((u = dir[i][0] + x) >= 0 && u<=n && (v = dir[i][1] + y) >= 0 && v <= n)
                dfs(u, v, l, r);
    }
     
    bool chk(int d, int u)
    {
        tim++;
        dfs(sx, sy, d, u);
        for (int i = 0; i < cnt; i++)
            if (vis[tx[i]][ty[i]] != tim)
                return false;
        return true;
    }
     
    int main()
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%s", s[i]);
            for(int j = 0; j < n; j++)
                if (s[i][j] == 'P')
                    sx = i, sy = j;
                else if (s[i][j] == 'K')
                    tx[cnt] = i, ty[cnt++] = j;
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &h[i][j]), sb[++sb[0]] = h[i][j];
        sort(sb + 1, sb + sb[0] + 1);
        sb[0] = unique(sb + 1, sb + sb[0] + 1) - sb - 1;
        for (int i = 1, j = 0; i <= sb[0]; i++)
            for (; j + 1 <= sb[0] && chk(sb[j + 1], sb[i]); j++)
                ans = min(ans, sb[i] - sb[j + 1]);
        printf("%d\n", ans);
        return 0;
    }
    

    最大用时:500ms

    总用时:2.2s

    • 2
      @ 2022-8-8 13:51:09

      暴力枚举+dfs+二分答案

      • 1

      信息

      ID
      1989
      时间
      4000ms
      内存
      256MiB
      难度
      2
      标签
      (无)
      递交数
      42
      已通过
      28
      上传者