kendas @ 2024-12-19 14:59:37
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int m;
const int N = 310;
vector<pair<PII,int>>q;
int g[N][N];
int dx[]{1,0,-1,0},dy[]{0,-1,0,1};
pair<PII,int> f[N*N];
int hh, tt = -1;
int bfs()
{
//记录当前坐标和当前时间
f[++ tt] = {{1,1},0};
while(hh <= tt)
{
auto t = f[hh ++];
//不在预测的-1位置,是安全点
if(g[t.first.first][t.first.second] == 0)
{
// cout << t.first.first << ' ' << t.first.second << endl;
return t.second;
}
//先砸下陨石看看
for(int i = 0; i < q.size(); i ++)
{
if(q[i].second <= t.second)
{
g[q[i].first.first][q[i].first.second] = 1;
for(int j = 0; j < 4; j ++)
{
int tx = q[i].first.first + dx[j],ty = q[i].first.second + dy[j];
if(tx >= 1 && ty >= 1)
g[tx][ty] = 1;
}
}
}
//发现自己被砸死
if(g[t.first.first][t.first.second] == 1)continue;
//没被砸死就进行瞎走
for(int i = 0; i < 4; i ++)
{
int tx = t.first.first + dx[i], ty = t.first.second + dy[i];
if(g[tx][ty] != 1 && tx >= 1 && ty >= 1)
{
f[++ tt] = {{tx,ty},t.second+1};
}
}
}
return -1;
}
int main()
{
cin>>m;
for(int i = 1; i <= m; i ++)
{
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
//以(1,1)为棋盘初始点
q.push_back({{x+1,y+1},t});
}
//先预测哪些点是安全点,将会被陨石砸的点标记为-1,这样之后bfs就可以知道自己是不是在安全点
for(int i = 0; i < q.size(); i ++)
{
g[q[i].first.first][q[i].first.second] = -1;
for(int j = 0; j < 4; j ++)
{
int tx = q[i].first.first + dx[j], ty = q[i].first.second + dy[j];
if(tx >= 1 && ty >= 1)
g[tx][ty] = -1;
}
}
cout << bfs();
}
by kendas @ 2024-12-24 15:11:22
@kendas
解决了,st数组应该提前标记,而不是不用或者再bfs尾部标记为true,会导致大量重复入队