_Ventus_ @ 2022-01-28 10:15:52
#include<bits/stdc++.h>
using namespace std;
int n,x,y,t;
int ma[301][301],v[301][301],ans[301][301];
int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
bool flag=true;
queue<int> q[2];
int ch(int a){
if(a==-1) return 99999;
else return a;
}
int main(){
cin>>n;
for(int i=0;i<301;i++){
for(int j=0;j<301;j++) ma[i][j]=-1;
}
for(int i=1;i<=n;i++){
cin>>x>>y>>t;
for(int j=0;j<=4;j++){
if(x+dx[j]>=0&&y+dy[j]>=0&&(ma[x+dx[j]][y+dy[j]]==-1||ma[x+dx[j]][y+dy[j]]>t)) ma[x+dx[j]][y+dy[j]]=t;
}
}
v[0][0]=1;
q[0].push(0),q[1].push(0);
while(!q[0].empty()){
int tx=q[0].front(),ty=q[1].front();
q[0].pop(),q[1].pop();
int s=ans[tx][ty]+1;
if(ma[tx][ty]==-1){
cout<<s-1;
flag=false;
break;
}
for(int i=1;i<=4;i++){
int sx=tx+dx[i],sy=ty+dy[i];
if(sx>=0&&sy>=0&&s<ch(ma[sx][sy])&&v[sx][sy]==0){
q[0].push(sx),q[1].push(sy);
v[sx][sy]=1,ans[sx][sy]=s;
}
}
}
if(flag) cout<<-1;
return 0;
}by Swiftie_wyc22 @ 2022-02-16 23:23:48
同问我也错在最后一点
by Swiftie_wyc22 @ 2022-02-16 23:28:23
啊我做出来了，我来帮你了~
判断的范围小了，你把判断下一个坐标放到400以内就可以。最后一个样例卡的很死
附上我的代码：
#include <bits/stdc++.h>
using namespace std;
int a[400][400], m;
bool vis[400][400];
struct node{
int x, y, time;
};
queue<node>q;
int dirx[] = {1, 0, -1, 0};
int diry[] = {0, 1, 0, -1};
signed main()
{
//freopen("C:\\Users\\33924\\Downloads\\P2895_14.in", "r", stdin);
for (int i = 0; i < 400; i++)
for (int j = 0; j < 400; j++)
a[i][j] = INT_MAX;
cin >> m;
int x, y, t;
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d", &x, &y, &t);
for (int k = 0; k < 4; k++)
if (x + dirx[k] >= 0 && y + diry[k] >= 0)
a[x + dirx[k]][y + diry[k]] = min(a[x + dirx[k]][y + diry[k]], t);
a[x][y] = min(a[x][y], t);
}
int tx = 0, ty = 0, time = 0;
q.push({tx, ty, time});
vis[tx][ty] = true;
while (!q.empty())
{
node f = q.front();
q.pop();
if (a[f.x][f.y] == INT_MAX)
{
cout << f.time << endl;
return 0;
}
for (int k = 0; k < 4; k++)
{
tx = f.x + dirx[k];
ty = f.y + diry[k];
if (tx >= 0 && ty >= 0 && tx < 400 && ty < 400 && a[tx][ty] > 0 && a[tx][ty] > f.time + 1 && !vis[tx][ty])
{
q.push({tx, ty, f.time + 1});
vis[tx][ty] = true;
}
}
}
cout << -1 << endl;
return 0;
}by 该不会是aha吧 @ 2022-03-05 12:17:57
@Aeterna 同问
by 该不会是aha吧 @ 2022-03-05 12:23:59
@Aeterna 为啥改成400就过了呀，我310也没有过，理论上比覆盖范围大2个格子应该就够了呀？求解答
by Swiftie_wyc22 @ 2022-03-05 16:29:04
@该不会是aha吧 sorry，这我就不清楚了，反正多开一些更保险
by m1saka @ 2022-03-05 20:09:08
同92，同改成400过了，只能说题目数据范围给得不好
by 该不会是aha吧 @ 2022-03-06 09:20:44
@Aeterna 我知道了，昨天上午刚写这题，下午校选拔赛就出了......开四百就过了的原因是，我们修改了判断是否越界的范围。题目给的流星雨的范围在300，但实际收到影响的范围应该在301，只要把那几个判断的范围改成302，数组开302也是能过的
by Swiftie_wyc22 @ 2022-03-06 20:54:54
@该不会是aha吧 明白了
by Harnue @ 2022-04-09 14:25:20
@该不会是aha吧 啥意思没看懂TwT，我把<=300改成<=301过了，但是应该不会影响结果啊
by 该不会是aha吧 @ 2022-04-10 17:42:11
@Akie_Qs aha，确实301没问题，题目极限就是301，不过我习惯性的，会想要比极限情况多开一点