90分#4求助,用的优先队列

P1434 [SHOI2002] 滑雪

hope88888888 @ 2022-03-02 17:07:41

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int num[102][102], r, c, dp[102][102], ans;
int dv[4][2] = { 1,0,-1,0,0,1,0,-1 };
struct NU {
    int value, x, y;
    bool operator < (const NU nu) const {
        return this->value < nu.value;
    }
};
priority_queue<NU> q;

inline NU make_nu(int value, int x, int y) {
    NU ans = { value,x,y };
    return ans;
}

int maxaround(int x, int y) {
    int ans = 0, xx, yy;
    for (int i = 0; i < 4; ++i) {
        xx = x + dv[i][0], yy = y + dv[i][1];
        ans = max(ans, dp[xx][yy] + (num[xx][yy] != num[x][y]));
    }
    return ans;
}

int main() {
    scanf("%d%d", &r, &c);
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            scanf("%d", &num[i][j]);
            q.push(make_nu(num[i][j], i, j));
        }
    }
    while (!q.empty()){
        NU t = q.top();
        q.pop();
        dp[t.x][t.y] = maxaround(t.x, t.y);
        ans = max(ans, dp[t.x][t.y]);
    }
    /*if (r == 1 && c == 1)printf("1");
    else*/ printf("%d", ans);
    return 0;
}

就是最后 return 0 之前那个注释那里,测试点#4的数据经过测试是1 1 1 答案为 1,我程序跑1 1 1的结果也是 1 ,但是就是wa,然后测完数据加个注释里的内容就过了,想请教一下为什么程序本身跑的 1 过不去


by oddy @ 2022-03-02 17:21:10

你的程序可能有 UB。


by hope88888888 @ 2022-03-02 17:44:23

@oddy 谢谢大佬,刚听你说完又去找了一下,发现把全局变量的ans设置成ans = 1就能ac了,不过不是很懂为什么会这样


|