28分bfs求调，后面十个点输出的全都是-1

M1saka16I72 @ 2023-11-14 10:46:52

by M1saka16I72 @ 2023-11-14 11:29:11

把memset语句里数组初值设置成0x3f之后#7 ac了，但其他测试点还是wa，35分

by M1saka16I72 @ 2023-11-14 17:39:41

已解决，错因：

设当前流星在t1时刻炸到的点的坐标为(nx,ny)

如果点(nx,ny)在t0时刻(t0<t1)被烧焦过，则(nx,ny)变得不安全的时间为t0，但被当前流星烧焦的点(dx,dy)变得不安全的时间应当被赋值为min(t1,t[dx][dy])，而不是min(t0,t[dx][dy])

ac代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int m;
const int INF = 0x3f3f3f3f;
int safety[305][305];
int ans[305][305];
bool vis[305][305];
int moves[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
void bfs(){
    int nx = 0,ny = 0;
    queue<int> qx,qy;
    qx.push(nx);qy.push(ny);
    int dx,dy;
    vis[nx][ny] = 1;
    while(!qx.empty() && !qy.empty()){
        nx = qx.front();ny = qy.front();
        // cout << nx << "." << ny <<"\n";
        qx.pop();qy.pop();
        for(int i=0;i<4;i++){
            dx = nx+moves[i][0];dy = ny+moves[i][1];
            if(dx>=0 && dy>=0 && !vis[dx][dy]){
                if(safety[dx][dy]>ans[nx][ny]+1){
                    if(safety[dx][dy]>99999){
                        cout << ans[nx][ny]+1;
                        exit(0);
                    }
                    else{
                        qx.push(dx);
                        qy.push(dy);
                        ans[dx][dy] = ans[nx][ny]+1;
                        vis[dx][dy] = 1;
                    }
                }
            }
        }
    }
}
int main(){
    memset(vis,0,sizeof(vis));
    memset(ans,0,sizeof(ans));
    memset(safety,0x3f,sizeof(safety));
    cin >> m;
    int x,y,t,dx,dy;
    for(int i=0;i<m;i++){
        cin >> x >> y >> t;
        safety[x][y] = min(safety[x][y],t);
        for(int j=0;j<4;j++){
            dx = x+moves[j][0];dy = y+moves[j][1];
            if(dx>=0 && dy>=0)    safety[dx][dy] = min(t,safety[dx][dy]);
        }
    }
    // for(int j=0;j<=8;j++){
    //     for(int k=0;k<=8;k++)   cout << j << " " << k <<" "<<safety[j][k]<<"\n";
    // }
    if(safety[x][y]==INF)   {cout << 0;return 0;}
    else if(safety[x][y]==0)    {cout << -1;return 0;}
    else    bfs();
    cout << -1;
    return 0;
}