谷歌Kickstart A 2021年-兔屋

Question

有人能告诉我我的密码出了什么问题吗？我已经通过了样本测试，但我不能通过两个实际的测试用例。

我的算法是dfs：

1. 从矩阵的第一个元素一直到最后，检查元素与相邻的上、下、左、右元素之间的差值是否小于或等于1

。

1. ，如果没有，则将最小块数添加到检查元素或相邻元素中，以使差异1，并将所添加的最小块数

增加。

1. 如何将最小数目添加到哪个元素:只需选择较小的元素，即使绝对差1

所需的最小值

例如，

1. 说，您将aij与较低的ai+1j进行了比较:如果添加到检查元素中是因为它较小，那么递归再次从aij+1开始，aij-1，ai-1j。因为现在aij和ai+1j之间的区别满足了标准，所以您需要检查是否与其他相邻的，否则递归从ai+1j

开始。

1. 为下、上、左、右的

做上面的阶梯

6.退回计数

这里有个问题： https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14

问题芭芭拉去年在学校取得了很好的成绩，所以她的父母决定送给她一只宠物兔子。她是如此兴奋，她为兔子建造了一座房子，它可以被看作是一个带有R行和C列的2D网格。

兔子喜欢跳，所以芭芭拉把几个盒子堆在网格的几个细胞上。每个框都是一个具有相同尺寸的立方体，与网格中的单元格的尺寸完全匹配。

然而，芭芭拉很快意识到，兔子跳高超过一个盒子可能是危险的，所以她决定通过对房子做一些调整来避免这种情况。每一对相邻的细胞，芭芭拉都希望它们的绝对高度差最多是一个盒子。如果两个细胞有共同的一面，它们就被认为是相邻的。

由于所有的盒子都是超粘的，芭芭拉无法移除最初存在的任何盒子，但是她可以在上面添加盒子。她可以随心所欲地把多少盒子加到多少个细胞里(可能是零)。帮助hew确定要添加的最小盒子总数，这样兔子的房子才是安全的。

输入输入的第一行给出测试用例的数量，T测试用例紧随其后。

每个测试用例都从包含两个整数R和C的一行开始。

然后，R线跟着，每一行都有C整数。第一行的第j个整数，Gi，j，表示网格第一行和第j列单元格上最初有多少个框。

输出每个测试用例，输出一行包含用例#x: y，其中x是测试用例号(从1开始)，y是要添加的最小框数，这样兔子的房子就安全了。

内存限制:1GB。1≤T≤100。0≤Gi，j≤2⋅106，i，j.测试集1时间限制:20秒.1≤R，C≤50。测试集2时间限制:40秒。1≤R，C≤300。

这是我在C++:中的代码

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>

using namespace std;

void solve(vector<vector<int>> &v,
    int ii, int jj,
    int r, int c, int& cnt) {
    if (ii<0 || ii>r - 1 || jj<0 || jj>c - 1) return;
    int ads;
    if (ii + 1 < r) {
        if (abs(v[ii][jj] - v[ii + 1][jj]) > 1) {
            ads = min(abs(v[ii + 1][jj] - v[ii][jj] - 1),
                abs(v[ii + 1][jj] - v[ii][jj] + 1));
                cnt += ads;
            if (v[ii + 1][jj] < v[ii][jj]) {
                v[ii + 1][jj] += ads;
                 solve(v, ii + 1, jj, r, c, cnt);
            }
            else {
                v[ii][jj] += ads;
                solve(v, ii, jj - 1, r, c, cnt);
                solve(v, ii, jj + 1, r, c, cnt);
                solve(v, ii - 1, jj, r, c, cnt);
            }
        }
    }
    if (ii - 1 > -1) {
        if (abs(v[ii][jj] - v[ii - 1][jj]) > 1) {
            ads = min(abs(v[ii - 1][jj] - v[ii][jj] - 1),
                abs(v[ii - 1][jj] - v[ii][jj] + 1));
                cnt += ads;
            if (v[ii - 1][jj] < v[ii][jj]) {
                v[ii - 1][jj] += ads;
                solve(v, ii - 1, jj, r, c, cnt);
            }
            else {
                v[ii][jj] += ads;
                solve(v, ii, jj - 1, r, c, cnt);
                solve(v, ii, jj + 1, r, c, cnt);
                solve(v, ii + 1, jj, r, c, cnt);
            }
        }
    }
    if (jj - 1 > -1) {
        if (abs(v[ii][jj] - v[ii][jj - 1]) > 1) {
            ads = min(abs(v[ii][jj - 1] - v[ii][jj] - 1),
                abs(v[ii][jj - 1] - v[ii][jj] + 1));
                cnt += ads;
            if (v[ii][jj - 1] < v[ii][jj]) {
                v[ii][jj - 1] += ads;
                solve(v, ii, jj - 1, r, c, cnt);
            }
            else {
                v[ii][jj] += ads;
                solve(v, ii, jj + 1, r, c, cnt);
                solve(v, ii - 1, jj, r, c, cnt);
                solve(v, ii + 1, jj, r, c, cnt);
            }
        }
    }
    if (jj + 1 < c) {
        if (abs(v[ii][jj] - v[ii][jj + 1]) > 1) {
            ads = min(abs(v[ii][jj + 1] - v[ii][jj] - 1),
                abs(v[ii][jj + 1] - v[ii][jj] + 1));
                cnt += ads;
            if (v[ii][jj + 1] < v[ii][jj]) {
                v[ii][jj + 1] += ads;
                solve(v, ii, jj + 1, r, c, cnt);
            }
            else {
                v[ii][jj] += ads;
                solve(v, ii, jj - 1, r, c, cnt);
                solve(v, ii - 1, jj, r, c, cnt);
                solve(v, ii + 1, jj, r, c, cnt);
            }
        }
    }
    return;
}

int main() {
        // your code goes here
        int t;
        cin>>t;
        int r, c, m;
        for (int i = 0; i < t; i++) {
            cin >> r >> c;
            vector<vector<int>> v(r,vector<int>(c,0));
            for (int j=0;j<r;j++){
                for (int k=0;k<c;k++){
                    cin>>m;
                    v[j][k]=m;
                }
            }
            int cnt=0;
            for (int j=0;j<r;j++){
                for (int k=0;k<c;k++){
                    solve(v,j,k,r,c,cnt);
                }
            }
            cout << "Case #" << i + 1 << ": " << cnt<<endl;
        }
        return 0;
}

我通过了样例:样例输入3 1 3 3 4 3 3 3 0 3 3 3 0 0 0样例输出例#1: 0 0例#2: 3例#3: 4

但是没有实际的测试cases...any帮助非常感谢！！

Answer 1

正如注释中已经指出的，解决方案是从最高框开始，并在需要时设置其邻居的高度值。

一个简单的实现是O(n^2)。

正如注释中所建议的那样，我尝试使用max-堆。但是，这个解决方案不够快(TLE)，因为一旦更新了矩阵的高度值，就必须重建最大堆。我可能有可能改进这个实现。我宁愿走另一条路。

最后，通过使用带有专用比较器的std::multiset，我得到了足够快的解决方案。

当单元格的高度被更新时，它被移除并重新插入到多个集合中，每个操作都是O(logn)。

全局复杂性: O(n logn)，其中n是矩阵的元素‘n=R* C*的个数。

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>

struct Coord {
    int x;
    int y;
    friend std::ostream& operator<<(std::ostream& os, const Coord& c) {
        os << "(" << c.x << ", " << c.y << ")";
        return os;
    }
};

long long int solution (std::vector<std::vector<int>>& heights, int R, int C) {
    std::vector<Coord> depl = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    long long int count = 0;
    auto Comp = [&heights] (const Coord& c0, const Coord& c1) {
        if (heights[c0.x][c0.y] == heights[c1.x][c1.y]) {
            if (c0.x == c1.x) return (c0.y < c1.y);
            return (c0.x < c1.x);
        }
        return heights[c0.x][c0.y] > heights[c1.x][c1.y];
    };
    
    std::multiset<Coord, decltype(Comp)> Cells (Comp);
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            Cells.insert ({i, j});
        }
    }

    auto isValid = [&] (int i, int j) {
        return (i >= 0) && (i < R) && (j >= 0) && (j < C);
    };
    
    while (Cells.size() > 1) {
        auto n = Cells.size();
        auto top = Cells.begin();
        auto pivot = *top;
        int h_ref = heights[pivot.x][pivot.y];
        Cells.erase (top);
        
        for (auto& d: depl) {
            int x = pivot.x + d.x;
            int y = pivot.y + d.y;
            if (!isValid(x, y)) continue;
            int h = heights[x][y];
            if (h <= h_ref - 2) {
                count += h_ref - h - 1;
                Cells.erase({x, y});
                heights[x][y] = h_ref - 1;
                Cells.insert({x, y});
            }
        }
    }
    return count;
}

int main() {
    std::ios_base::sync_with_stdio(false); 
    std::cin.tie(NULL); 
    std::cout.tie(0);
    int nt;
    std::cin >> nt;
    for (int t = 1; t <= nt; t++) {
        int R, C;
        std::cin >> R >> C;
        std::vector<std::vector<int>> v(R, std::vector<int>(C));
        for (int j = 0; j < R; j++) {
            for (int k = 0; k < C; k++) {
                int m;
                std::cin >> m;
                v[j][k] = m;
            }
        }
        auto cnt = solution (v, R, C);
        std::cout << "Case #" << t << ": " << cnt << std::endl;
    }
    return 0;
}