0分求助orz

P2895 [USACO08FEB] Meteor Shower S

残阳如血 @ 2023-07-15 20:31:53

```cpp #include <bits/stdc++.h> using namespace std; const int SIZE = 1 << 14; int M, t, p, now[400][400], safe[400][400], ans[400][400]; int walk[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; struct meteor { int X, Y, T; } danger[50010]; struct place { int x, y; }; char getc() { static char buf[SIZE], *begin = buf, *end = buf; if (begin == end) { begin = buf; end = buf + fread(buf, 1, SIZE, stdin); } return *begin++; } int read() { int sgn = 0, ret = 0, ch = getc(); while (!isdigit(ch) && ch != EOF) ch |= ch == '-', ch = getc(); while (isdigit(ch) && ch != EOF) ret = ret * 10 + ch - '0', ch = getc(); return sgn ? -ret : ret; } void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); return; } bool cmp(meteor a, meteor b) { if (a.T == b.T) { if (a.X == b.X) return a.Y < b.Y; return a.X < b.X; } return a.T < b.T; } bool inRange(int x, int y) { if (x < 0 || y < 0) return false; return true; } int main() { queue<place> q; cin >> M; memset(safe, -1, sizeof(safe)); for (int i = 0; i < M; i++) { danger[i].X = read(), danger[i].Y = read(), danger[i].T = read(); safe[danger[i].X][danger[i].Y] = 0; for (int k = 0; k < 4; k++) { int newx = danger[i].X + walk[k][0]; int newy = danger[i].Y + walk[k][1]; if (!inRange(newx, newy)) continue; safe[newx][newy] = 0; } } sort(danger, danger + M, cmp); q.push({0, 0}); ans[0][0] = 1; while (!q.empty()) { auto cur = q.front(); q.pop(); while (danger[p].T == t) now[danger[p].X][danger[p].Y] = -1, p++; t++; if (safe[cur.x][cur.y]) { cout << ans[cur.x][cur.y] - 1; return 0; } for (int i = 0; i < 4; i++) { int newx = cur.x + walk[i][0]; int newy = cur.y + walk[i][1]; if (!inRange(newx, newy)) continue; if (ans[newx][newy] || now[newx][newy] == -1) continue; q.push({newx, newy}); ans[newx][newy] = ans[cur.x][cur.y] + 1; } } cout << -1; return 0; } ```

by 残阳如血 @ 2023-07-15 20:32:26

不知道为什么样例输出的是 3。

by hjczmf @ 2023-07-22 13:12:11

@BHPM 我电脑上CE了

by hjczmf @ 2023-07-22 13:16:54

61行、66行、71行

cur 缺少头文件

cur 未定义

电脑报错的

我想问：为啥万能头会缺少头文件？

by cat_lover1 @ 2023-09-20 16:11:14

@残阳如血 我代码输出也是3，完全蒙了，不知道哪儿有问题。我觉得我们思路差不多，我这个代码加了一些输出调试

typedef struct queue{int x,y,t}queue;
_Bool notsafe[301][301];
M,T[50000],X[50000],Y[50000],d[301][301];
dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
_Bool H[301][301];L;
/*Qsort(L,R){
  if(L>=R)return;
  int I=L,J=R,xT=t[L],xX=X[L],xY=Y[L],tT,tX,tY;
  do{
    while(I<J&&T[J]>xT)--J;
    if(I<J)tT=xT,xT=T[J],T[j]=tT,tX=xX,xX=X[j],X[j]=tX,tY=xY,xY=Y[j],Y[j]=tY;
    while(i<j&&T[i]<xT)++i;
    if(i<j)tT=xT,xT=T[j],T[j]=tT,tX=xX,xX=X[j],X[j]=tX,tY=xY,xY=Y[j],Y[j]=tY;
  }while(I<J);
  T[L]=xT,X[L]=xX,Y[L]=xY;
  qsort(L,)
}*/
Check(Time){
  int i;
  for(i=L;i<M;++i)
    if(T[i]==Time){
      H[X[i]][Y[i]]=1;
      for(int j=0;j<4;++j){
        int x=X[i]+dx[j],y=Y[i]+dy[j];
        if(x>=0&&x<=300&&y>=0&&y<=300)
          H[x][y]=1;
      }
    }
  L=i;
}
BFS(x,y){
  //putchar('0');
  d[x][y]=0;
  queue Q[100000];
  //putchar('1');
  int head=0,tail=1,Time=0;
  Q[0].x=x,Q[0].y=y,Q[0].t=0;
  Check(Time);
  do{//putchar('1');
    queue f=Q[head++];
    if(!notsafe[f.x][f.y])
      return d[f.x][f.y];
    if(f.t>Time-1)
      Check(++Time);
    printf("fx=%d fy=%d ft=%d ",f.x,f.y,f.t);
    for(int i=0;i<4;++i){
      int x=f.x+dx[i],y=f.y+dy[i];
      if(x>=0&&x<=300&&y>=0&y<=300
           &&!H[x][y]&&d[x][y]==-1)printf("x=%d y=%d ",x,y),
        Q[tail].x=x,Q[tail].y=y,
        Q[tail++].t=d[x][y]=d[f.x][f.y]+1;
    }
    printf("head=%d tail=%d\n",head,tail);
  }while(head<tail);
  return -1;
}
main(){
  memset(d,-1,sizeof(d));
  scanf("%d",&M);
  for(int i=0;i<M;++i){
    scanf("%d%d%d",X+i,Y+i,T+i),notsafe[X[i]][Y[i]]=1;
    for(int j=0;j<4;++j){
      int x=X[i]+dx[j],y=Y[i]+dy[j];
      if(x>=0&&x<=300&y>=0&&y<=300)
        notsafe[x][y]=1;
    }  
  }
  printf("%d",BFS(0,0));
}
|