Karl_Wan @ 2024-10-23 14:37:41

#include <iostream>
#include <queue>
using namespace std;
int m;
int danger[305][305];
void add(int x,int y,int t)
{
    danger[x][y]=t;
    if(x>0) danger[x-1][y]=t;
    if(y>0) danger[x][y-1]=t;
    danger[x+1][y]=danger[x][y+1]=t;
}
struct node
{
    int x,y,dis;
};
bool vis[305][305];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
queue<node> q;
int bfs()
{
    q.push({0,0,0});
    vis[0][0]=1;
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(danger[now.x][now.y]==(-1))
        {
            return now.dis;
        }
        for(int i=0;i<4;i++)
        {
            int tx=now.x+dir[i][0];
            int ty=now.y+dir[i][1];
            if(tx>=0&&ty>=0&&tx<=300&&ty<=300)
            {
                if(!vis[tx][ty]&&(danger[tx][ty]==(-1)||danger[tx][ty]>now.dis+1))
                {
                    vis[tx][ty]=1;
                    q.push({tx,ty,now.dis+1});
                }
            }
        }
    }
    return -1;
}
int main()
{
    for(int i=0;i<=300;i++)
    {
        for(int j=0;j<=300;j++) danger[i][j]=(-1);
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,t;
        cin>>x>>y>>t;
        add(x,y,t);
    }
    cout<<bfs(); 

    return 0;
}

by Lbj080617 @ 2024-10-23 15:21:56

@Karl_Wan 我觉得你wa65分的原因是你没有考虑人是可以到x>300,y>300的地方的（题目里只说了陨石砸在(0≤Xi≤300，0≤Yi≤300)的地方，而人没有限制（即人的x,y是可以大于300的））。

by Karl_Wan @ 2024-10-23 15:22:58

@Lbj080617 谢dalao！

by Karl_Wan @ 2024-10-23 16:00:28

@Lbj080617 可是改了没多大用，还是会WA （记录）

by Lbj080617 @ 2024-10-23 16:07:26

看了一下你的代码，我觉得你可能需要开两个二维数组，一个用来存某块地什么时候被破坏，一个用来存从起点到每一块地的时间。```c

include <bits/stdc++.h>

using namespace std; struct ys { int x,y; }; queue <ys> q; int m,ans,ma[350][350],die[350][350],sz[4] = {0,1,0,-1},sp[4] = {1,0,-1,0},ti = 1e9; void fz(int x,int y,int t) { if(x >= 0 && y >= 0) die[x][y] = min(die[x][y],t); return; } int main() { cin >> m; memset(ma,-1,sizeof(ma)); memset(die,0x7f7f7f7f,sizeof(die)); for(int i = 1;i <= m;i++) { int a,b,c; cin >> a >> b >> c; fz(a,b,c); for(int j = 0;j < 4;j++) fz(a + sz[j],b + sp[j],c); } q.push((ys){0,0}); ma[0][0] = 0; while(!q.empty()) { int lx = q.front().x,ly = q.front().y; q.pop(); for(int i = 0;i < 4;i++) { int fx = lx + sz[i],fy = ly + sp[i]; if(fx < 0 || fy < 0 || ma[fx][fy] != -1 || ma[lx][ly] + 1 >= die[fx][fy]) continue; ma[fx][fy] = ma[lx][ly] + 1; q.push((ys){fx,fy}); } } for(int i = 0;i <= 305;i++) for(int j = 0;j <= 305;j++) if(die[i][j] >= 1000 && ma[i][j] + 1) ti = min(ti,ma[i][j]); if(ti == 1e9) cout << "-1"; else cout << ti; return 0; }

by Lbj080617 @ 2024-10-23 16:10:50

c #include <bits/stdc++.h> 
using namespace std; 
struct ys { int x,y; }; 
queue <ys> q; 
int m,ans,ma[350][350],die[350][350],sz[4] = {0,1,0,-1},sp[4] = {1,0,-1,0},ti = 1e9; 
void fz(int x,int y,int t) 
{ 
  if(x >= 0 && y >= 0) 
    die[x][y] = min(die[x][y],t); 
  return; 
} 
int main() 
{ 
  cin >> m; 
  memset(ma,-1,sizeof(ma)); 
  memset(die,0x7f7f7f7f,sizeof(die));
  for(int i = 1;i <= m;i++) 
  { 
    int a,b,c; cin >> a >> b >> c;
    fz(a,b,c); 
    for(int j = 0;j < 4;j++)
      fz(a + sz[j],b + sp[j],c); 
  }
  q.push((ys){0,0});
  ma[0][0] = 0; 
  while(!q.empty()) 
  { int lx = q.front().x,ly = q.front().y;
   q.pop();
   for(int i = 0;i < 4;i++) 
   { 
     int fx = lx + sz[i],fy = ly + sp[i]; 
     if(fx < 0 || fy < 0 || ma[fx][fy] != -1 || ma[lx][ly] + 1 >= die[fx][fy])
       continue; 
     ma[fx][fy] = ma[lx][ly] + 1; 
     q.push((ys){fx,fy});
   } 
  } 
  for(int i = 0;i <= 305;i++) 
    for(int j = 0;j <= 305;j++) 
      if(die[i][j] >= 1000 && ma[i][j] + 1) ti = min(ti,ma[i][j]); 
  if(ti == 1e9) 
    cout << "-1"; 
  else cout << ti;
  return 0; 
}

这才是我的代码（刚才不知道怎么了没有插入成功）

by Lbj080617 @ 2024-10-23 16:12:46

@Karl_Wan 在不

by Karl_Wan @ 2024-10-23 16:22:19

@Lbj080617 在

by Lbj080617 @ 2024-10-23 16:24:40

@Karl_Wan 懂了吗？

by Karl_Wan @ 2024-10-23 16:27:27

@Lbj080617 懂了，谢谢！