DougNo1 @ 2024-07-14 10:47:54
代码：
#include <bits/stdc++.h>
using namespace std;
struct point{
int x,y;//坐标
int t,step;//t:流星落下的时间 step:走到这里用的步数
bool b;//是否走过(0:没走过 1:走过）
}a[305][305];
int main(){
//输入n 结构体初始化
int n;
cin>>n;
for(int i=1;i<=300;i++){
for(int j=1;j<=300;j++){
a[i][j].x = i;
a[i][j].y = j;
a[i][j].t = -1;
a[i][j].step = 100000;
a[i][j].b = 0;
}
}
//输入其他数据 做标记
int dx[6]={0,-1,1,0,0,0},dy[6]={0,0,0,-1,1,0};
for(int i=1;i<=n;i++){
int xx,yy,tt;
cin>>xx>>yy>>tt;
xx++,yy++;
for(int j=1;j<=5;j++){
if(xx+dx[j]<1 || yy+dy[j]<1) continue;
a[xx+dx[j]][yy+dy[j]].t=tt;
}
}
//创建队列 队列初始化
queue<point> q;
a[1][1].step=0;
a[1][1].b=1;
q.push(a[1][1]);
//BFS
while(!q.empty()){
point p=q.front();
q.pop();
for(int i=1;i<=4;i++){
int xx=p.x+dx[i], yy=p.y+dy[i];
if(xx<1 || yy<1 || a[xx][yy].b==1) continue;
if(a[xx][yy].t == -1){
cout<<p.step+1;
return 0;
}
if(p.step+1<a[xx][yy].t){
a[xx][yy].x=xx;
a[xx][yy].y=yy;
a[xx][yy].b=1;
a[xx][yy].step=p.step+1;
q.push(a[xx][yy]);
}
}
}
cout<<-1;
return 0;
}
提交记录
请大佬们帮我调一下代码！
by NOIP__qwq__ @ 2024-07-14 10:52:25
只有当这颗流星到达的时间小于前面流星到达的时间，才能把时间赋值给数组，而不能直接覆盖
by NOIP__qwq__ @ 2024-07-14 10:53:25
如果不考虑，只能得35分
by NOIP__qwq__ @ 2024-07-14 10:59:57
@Dougno1 OK
by hutao_262218926 @ 2024-07-14 11:16:36
这么改只能92吧
by DougNo1 @ 2024-07-14 12:51:52
@wangjunyia 改后代码：
#include <bits/stdc++.h>
using namespace std;
struct point{
int x,y;//坐标
int t,step;//t:流星落下的时间 step:走到这里用的步数
bool b;//是否走过(0:没走过 1:走过）
}a[305][305];
int main(){
//输入n 结构体初始化
int n;
cin>>n;
for(int i=1;i<=300;i++){
for(int j=1;j<=300;j++){
a[i][j].x = i;
a[i][j].y = j;
a[i][j].t = 1000;
a[i][j].step = 100000;
a[i][j].b = 0;
}
}
//输入其他数据 做标记
int dx[6]={0,-1,1,0,0,0},dy[6]={0,0,0,-1,1,0};
for(int i=1;i<=n;i++){
int xx,yy,tt;
cin>>xx>>yy>>tt;
xx++,yy++;
for(int j=1;j<=5;j++){
int x1=xx+dx[j],y1=yy+dy[j];
if(x1<1 || y1<1 || a[x1][y1].t<tt) continue;
a[x1][y1].t=tt;
}
}
//创建队列 队列初始化
queue<point> q;
a[1][1].step=0;
a[1][1].b=1;
q.push(a[1][1]);
//BFS
while(!q.empty()){
point p=q.front();
q.pop();
for(int i=1;i<=4;i++){
int xx=p.x+dx[i], yy=p.y+dy[i];
if(xx<1 || yy<1 || a[xx][yy].b==1 || p.step+1>=a[xx][yy].t) continue;
if(a[xx][yy].t == 1000){
cout<<p.step+1;
return 0;
}
a[xx][yy].x=xx;
a[xx][yy].y=yy;
a[xx][yy].b=1;
a[xx][yy].step=p.step+1;
q.push(a[xx][yy]);
}
}
cout<<-1;
return 0;
}
提交记录
只有92分
by DougNo1 @ 2024-07-14 13:24:08
@hutao_262218926
#include <bits/stdc++.h>
using namespace std;
struct point{
int x,y;//坐标
int t,step;//t:流星落下的时间 step:走到这里用的步数
bool b;//是否走过(0:没走过 1:走过）
}a[305][305];
int main(){
//输入n 结构体初始化
int n;
cin>>n;
for(int i=1;i<=300;i++){
for(int j=1;j<=300;j++){
a[i][j].x = i;
a[i][j].y = j;
a[i][j].t = 1000;
a[i][j].step = 100000;
a[i][j].b = 0;
}
}
//输入其他数据 做标记
int dx[6]={0,-1,1,0,0,0},dy[6]={0,0,0,-1,1,0};
for(int i=1;i<=n;i++){
int xx,yy,tt;
cin>>xx>>yy>>tt;
xx++,yy++;
for(int j=1;j<=5;j++){
int x1=xx+dx[j],y1=yy+dy[j];
if(x1<1 || y1<1 || a[x1][y1].t<tt) continue;
a[x1][y1].t=tt;
}
}
//创建队列 队列初始化
queue<point> q;
a[1][1].step=0;
a[1][1].b=1;
q.push(a[1][1]);
//BFS
while(!q.empty()){
point p=q.front();
q.pop();
for(int i=1;i<=4;i++){
int xx=p.x+dx[i], yy=p.y+dy[i];
if(xx<1 || yy<1 || a[xx][yy].b==1 || p.step+1>=a[xx][yy].t) continue;
if(a[xx][yy].t == 1000){
cout<<p.step+1;
return 0;
}
a[xx][yy].x=xx;
a[xx][yy].y=yy;
a[xx][yy].b=1;
a[xx][yy].step=p.step+1;
q.push(a[xx][yy]);
}
}
cout<<-1;
return 0;
}
确实只有92分
by hutao_262218926 @ 2024-07-14 14:01:49
不要用一千，用1001，t最大1000
by hutao_262218926 @ 2024-07-14 14:22:06
#include <bits/stdc++.h>
using namespace std;
struct point{
int x,y;//坐标
int t,step;//t:流星落下的时间 step:走到这里用的步数
bool b;//是否走过(0:没走过 1:走过）
}a[305][305];
int main(){
//输入n 结构体初始化
int n;
cin>>n;
for(int i=0;i<=301;i++){
for(int j=0;j<=301;j++){
a[i][j].x = i;
a[i][j].y = j;
a[i][j].t = 1001;
a[i][j].step = 100000;
a[i][j].b = 0;
}
}
//输入其他数据 做标记
int dx[6]={0,-1,1,0,0,0},dy[6]={0,0,0,-1,1,0};
for(int i=0;i<n;i++){
int xx,yy,tt;
cin>>xx>>yy>>tt;
for(int j=1;j<=5;j++){
int x1=xx+dx[j],y1=yy+dy[j];
if(x1<0 || y1<0 || a[x1][y1].t<tt) continue;
a[x1][y1].t=tt;
}
}
//创建队列 队列初始化
queue<point> q;
a[0][0].step=0;
a[0][0].b=1;
q.push(a[0][0]);
//BFS
while(!q.empty()){
point p=q.front();
q.pop();
for(int i=1;i<=4;i++){
int xx=p.x+dx[i], yy=p.y+dy[i];
if(xx<0 || yy<0 || a[xx][yy].b==1 || p.step+1>=a[xx][yy].t) continue;
if(a[xx][yy].t == 1001){
cout<<p.step+1;
return 0;
}
a[xx][yy].b=1;
a[xx][yy].step=p.step+1;
q.push(a[xx][yy]);
}
}
cout<<-1;
return 0;
}by hutao_262218926 @ 2024-07-14 14:24:42
从0开始比较好，题目说在（0，0）开始