大佬,求救!!!

P2895 [USACO08FEB] Meteor Shower S

违规用户名690561 @ 2022-07-23 10:33:48

最后3个点WA了……

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
struct node {
    long long x1, y1, z1;
} t1, s;
queue<node> q;
long long m, t[1005], x[1005], y[1005], a[400][400], b[400][400];
int dx[] = {-1, 1, 0, 0, 0};
int dy[] = {0, 0, -1, 1, 0};
void BFS(int xx, int yy, int zz) {
    t1 = {xx, yy, zz};
    q.push(t1);
    while(!q.empty()) {
        t1 = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            int xxx = t1.x1 + dx[i];
            int yyy = t1.y1 + dy[i];
            if(xxx >= 0 && yyy >= 0 && b[xxx][yyy] == 0) {
                b[xxx][yyy] = 1;
                if(c[xxx][yyy] == 0) {
                    printf("%d", t1.z1 + 1);
                    exit(0);
                } else {
                    s = {xxx, yyy, t1.z1 + 1};
                    if(s.z1 < a[xxx][yyy] - 1) {
                        q.push(s);
                    }
                }
            }
        }
    }
}
int main() {
    scanf("%d", &m);
    b[0][0] = 1;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &x[i], &y[i], &t[i]);
        if(a[x[i]][y[i]] == 0) {
            a[x[i]][y[i]] = t[i] + 1;
        }else{
            if(a[x[i]][y[i]] > t[i] + 1){
                a[x[i]][y[i]] = t[i] + 1;
            }
        }
        if(a[x[i]][y[i]] != 0){
            c[x[i]][y[i]] = 1;
        }
        if(x[i] - 1 >= 0) {
            if(a[x[i] - 1][y[i]] == 0){
                a[x[i] - 1][y[i]] = t[i] + 1;
            }else{
                if(a[x[i] - 1][y[i]] > t[i] + 1){
                    a[x[i] - 1][y[i]] = t[i] + 1;
                }
            }
        }
        if(a[x[i] - 1][y[i]] != 0){
            c[x[i] - 1][y[i]] = 1;
        }
        if(y[i] - 1 >= 0) {
            if(a[x[i]][y[i] - 1] == 0){
                a[x[i]][y[i] - 1] = t[i] + 1;
            }else{
                if(a[x[i]][y[i] - 1] > t[i] + 1){
                    a[x[i]][y[i] - 1] = t[i] + 1;
                }
            }
        }
        if(a[x[i]][y[i] - 1] != 0){
            c[x[i]][y[i] - 1] = 1;
        }
        if(a[x[i] + 1][y[i]] == 0) {
            a[x[i] + 1][y[i]] = t[i] + 1;
        }else{
            if(a[x[i] + 1][y[i]] > t[i] + 1){
                a[x[i] + 1][y[i]] = t[i] + 1;
            }
        }
        if(a[x[i] + 1][y[i]] != 0){
            c[x[i] + 1][y[i]] = 1;
        }
        if(a[x[i]][y[i] + 1] == 0) {
            a[x[i]][y[i] + 1] = t[i] + 1;
        }else{
            if(a[x[i]][y[i] + 1] > t[i] + 1){
                a[x[i]][y[i] + 1] = t[i] + 1;
            }
        }
        if(a[x[i]][y[i] + 1] != 0){
            c[x[i]][y[i] + 1] = 1;
        }
    }
    BFS(0, 0, 0);
    printf("-1");
    return 0;
}
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀⠛⠿⠿⣿⠃⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀

by Cutata @ 2022-07-29 14:52:53

建议先改改码风!


by 违规用户名690561 @ 2022-07-29 16:46:26

@JokerYI

什么意思?能详细讲讲吗?


by Cutata @ 2022-07-30 14:03:08

@tzxxzt 主函数给地图赋初值可以循环跑一遍方位数组,减少码量,否则容易出错。

for(int i = 1; i <= m; i++){
        cin >> fx >> fy >> ft;
        for(int j = 0; j < 5; j++){
            int nx = fx + dx[j];
            int ny = fy + dy[j];
            if(nx >= 0 and ny >= 0){
                if(vis[nx][ny] >= 0)
                    vis[nx][ny] = min(vis[nx][ny], ft);
                else
                    vis[nx][ny] = ft;
            }

        }
    }

和你的风格可能不太一样,希望对你有帮助。


by 违规用户名690561 @ 2022-08-03 13:32:54

@JokerYI 谢谢


|