[c艹] #14WA 求助大佬

D_guard @ 2022-09-15 17:42:16

459

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define stn frm[x + trn[i][0] + 1][y + trn[i][1] + 1]
#define nxtx x.x + trn[i][0]
#define nxty x.y + trn[i][1]
#define m10(x) ((x << 3) + (x << 1))
using namespace std;

int m, x, y, t, frm[303][303];
int trn[5][2] = {0, 0, -1, 0, 1, 0, 0, -1, 0, 1};

struct pos {int x, y, t;} np;

queue<pos> q;

inline int qread()
{
    int tmp = getchar(), ot = 0;
    while (tmp < '0' || tmp > '9')
        tmp = getchar();
    while (tmp >= '0' && tmp <= '9')
    {
        ot = m10(ot);
        ot += tmp ^ 48;
        tmp = getchar();
    }
    return ot;
}

inline int bfs()
{
    while (!q.empty())
    {
        pos x = q.front();
        q.pop();
        for (int i = 1; i < 5; ++i)
        {
            if (frm[nxtx][nxty] <= x.t)
                continue;
            if (nxtx < 1 || nxtx > 301 || nxty < 1 || nxty > 301)
                continue;
            if (frm[nxtx][nxty] == 0x3f3f3f3f)
                return x.t;
            frm[nxtx][nxty] = -1;
            np.x = nxtx, np.y = nxty, np.t = x.t + 1;
            q.push(np);
        }
    }
    return -1;
}

int main()
{
    memset(frm, 0x3f, sizeof(frm));
    m = qread();
    while (m--)
    {
        x = qread();
        y = qread();
        t = qread();
        for (int i = 0; i < 5; ++i)
            stn = min(stn, t);
    }
    if(frm[1][1] == 0x3f3f3f3f)
    {
        printf("0");
        return 0;
    }
    np.x = np.y = np.t = 1;
    frm[1][1] = -1;
    q.push(np);
    printf("%d", bfs());
    return 0;
}

by haomeitui @ 2022-09-15 18:00:17

借我一个亿吧

by yuhaocheng @ 2022-09-15 18:51:09

开个long long试试？

by yuhaocheng @ 2022-09-15 18:52:26

@D_guard

by D_guard @ 2022-09-15 19:12:12

@yuhaocheng

您是指哪里开long long？就我所见，本题数据m、坐标、时间都在int范围内啊

by D_guard @ 2022-09-27 17:16:08

找到问题了：

它只能在第一象限中，平行于坐标轴行动

没有最大值的限制，所以贝茜的坐标可以超过300...

#14就是在坐标为302 时来到没有被砸到过的

by D_guard @ 2022-09-27 17:16:27

此贴完

by little__bird @ 2022-10-20 00:03:27

这是真坑，我说为啥最后一个点WA

by ___A__ @ 2023-01-16 14:00:28

@little__bird 你说的不对吧

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=300+50;
int n,t,x,y,ans[N][N],vis[N][N],dx[5]={-1,1,0,0,0},dy[5]={0,0,-1,1,0};//vis代表有没有被撅过
struct node{
    int x,y;    
};
void bfs(){
    queue<node>q;
    q.push({0,0});
    ans[0][0]=0;
    while(!q.empty()){
        node u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int row=u.x+dx[i],col=u.y+dy[i];
            if(row>=0&&row<=300&&col>=0&&col<=300&&ans[row][col]==-1&&vis[row][col]>ans[u.x][u.y]+1){
                ans[row][col]=ans[u.x][u.y]+1;
                q.push({row,col});
            }
        }
    }
}
signed main(){
    cin>>n;
    memset(ans,-1,sizeof(ans));
    memset(vis,100,sizeof(vis));
    while(n--){
        cin>>x>>y>>t;
        for(int i=0;i<5;i++){
            int row=x+dx[i],col=y+dy[i];
            if(row>=0&&row<=300&&col>=0&&col<=300){
                vis[row][col]=min(t,vis[row][col]);
            }
        }
    }
    bfs();
    int Ans=114514;
    for(int i=0;i<350;i++){
        for(int j=0;j<350;j++){         
            if(vis[i][j]>10000&&ans[i][j]!=-1){
                Ans=min(Ans,ans[i][j]);
            }
        }
    }
    if(Ans==114514){
        Ans=-1;
    }
    cout<<Ans;
}

这样照样最后一个点WA

by Lucre @ 2023-03-27 15:42:43

@D_guard 。。。真的坑啊

by 程序小大白 @ 2023-04-24 15:59:18

也就是说 炸弹只能在0~300掉落，而主人公可以在第一象限任何位置（0~300以外也可）移动