SUPERLWR @ 2021-08-19 11:15:33
#include<bits/stdc++.h>
using namespace std;
int m,x,y,t,g[305][305],f[305][305],visit[305][305];
struct zb{
int x,y;
};
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
queue<zb> q;
cin>>m;
for(int i=0;i<=304;i++)
for(int j=0;j<=304;j++)
g[i][j]=-1;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>t;
if(g[x][y]==-1||g[x][y]>t)
g[x][y]=t;
if(g[x+1][y]==-1||g[x+1][y]>t)
g[x+1][y]=t;
if(g[x][y+1]==-1||g[x][y+1]>t)
g[x][y+1]=t;
if(x-1>=0)
if(g[x-1][y]==-1||g[x-1][y]>t)
g[x-1][y]=t;
if(y-1>=0)
if(g[x][y-1]==-1||g[x][y-1]>t)
g[x][y-1]=t;
/*for(int k=0;k<=5;k++)
{
for(int j=0;j<=5;j++)
printf("%-4d",g[k][j]);
cout<<endl;
}*/
}
zb now;
now.x=0;now.y=0;
q.push(now);
visit[0][0]=1;
int xx,yy;
while(!q.empty())
{
now=q.front();
q.pop();
xx=now.x,yy=now.y;
//cout<<"坐标："<<xx<<" "<<yy<<"步数："<<f[xx][yy]<<"\n";
if(g[xx][yy]==-1)
{
// cout<<"\n跳出\n";
break;
}
if(f[xx][yy]<g[xx+1][yy]-1&&!visit[xx+1][yy]||g[xx+1][yy]==-1)
{
visit[xx+1][yy]=1;
zb tmp;
tmp.x=xx+1;tmp.y=yy;
q.push(tmp);
f[xx+1][yy]=f[xx][yy]+1;
// cout<<"下\n";
}
if(xx-1>=0)
if(f[xx][yy]<g[xx-1][yy]-1&&!visit[xx-1][yy]||g[xx-1][yy]==-1)
{
visit[xx][yy+1]=1;
zb tmp;
tmp.x=xx;tmp.y=yy;
q.push(tmp);
f[xx-1][yy]=f[xx][yy]+1;
// cout<<"上\n";
}
if(f[xx][yy]<g[xx][yy+1]-1&&!visit[xx][yy+1]||g[xx][yy+1]==-1)
{
visit[xx-1][yy]=1;
zb tmp;
tmp.x=xx;tmp.y=yy+1;
q.push(tmp);
f[xx][yy+1]=f[xx][yy]+1;
// cout<<"右\n";
}
if(yy-1>=0)
if(f[xx][yy]<g[xx][yy-1]-1&&!visit[xx][yy-1]||g[xx][yy-1]==-1)
{
visit[xx][yy-1]=1;
zb tmp;
tmp.x=xx;tmp.y=yy-1;
q.push(tmp);
f[xx][yy-1]=f[xx][yy]+1;
// cout<<"左\n";
}
}
if(g[xx][yy]==-1)
cout<<f[xx][yy];
else
cout<<-1;
return 0;
}debug时候的注释没删，请忽略
by SUPERLWR @ 2021-08-19 11:16:05
https://www.luogu.com.cn/record/56346444
by wangshirui001 @ 2021-08-19 11:53:39
你可以试试输出中间变量或者参考题解改改。
by _ROSE_ @ 2021-08-19 11:54:33
https://www.luogu.com.cn/record/53405240
by jjltcl_ac @ 2021-08-19 11:55:01
@wangshirui001 玩梗小鬼怕爬啊
by SUPERLWR @ 2021-08-19 11:55:27
@wangshirui001 输出中间变量是啥意思？
已经照着题解改了蛮久了
by SUPERLWR @ 2021-08-19 11:56:52
@刘念森 dalao我没到60分看不到代码qwq
by _ROSE_ @ 2021-08-19 12:10:06
@SUPERLWR
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
struct node {
int x,y,time;
} p;
int m,x,y,t,time1[305][305],vis[305][305];
int dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
queue<node>q;
int main() {
cin>>m;
for(int i=0; i<=302; i++) {
for(int j=0; j<=302; j++) {
time1[i][j]=-1;
}
}
for(int i=1; i<=m; i++) {
cin>>x>>y>>t;
if(t<time1[x][y]||time1[x][y]==-1)
time1[x][y]=t;
for(int i=0; i<4; i++) {
int nx=x+dir[i][0],ny=y+dir[i][1];
if(nx>=0&&ny>=0&&(time1[nx][ny]==-1||t<time1[nx][ny])){
time1[nx][ny]=t;
}
}
}
p.x=0,p.y=0,p.time=0,vis[0][0]=1;
q.push(p);
while(!q.empty()) {
p=q.front();
q.pop();
for(int i=0; i<4; i++) {
int nx=p.x+dir[i][0],ny=p.y+dir[i][1];
if(nx>=0&&ny>=0&&vis[nx][ny]==0&&(time1[nx][ny]==-1||p.time+1<time1[nx][ny])) {
node u;
u.x=nx;
u.y=ny;
u.time=p.time+1;
vis[nx][ny]=1;
q.push(u);
if(time1[nx][ny]==-1) {
printf("%d",u.time);
return 0;
}
}
}
}
printf("-1");
return 0;
}简单的bfs （逃）