RE 14分 求助

方俊懿 @ 2020-10-16 22:18:18

#include <cstdio>
#define Hello input();
#define World printf("%d",solve())
void input();
int solve();
int main()
{
    Hello World;
    return 0;
}
int n,t[50005],x[50005],y[50005];
int timeQ[3600000],xQ[3600000],yQ[3600000],head,tail=1;
bool book[605][605];
int d[2][4]={{0,0,-1,1},{-1,1,0,0}};
void input()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d%d",&x[i],&y[i],&t[i]);
}
bool check(int xx,int yy,int time)
{
    bool map[605][605]={};
    for(int i=0;i<n;i++)
        if(t[i]<=time)
        {
            map[x[i]][y[i]]=1;
            map[x[i]+1][y[i]]=1;
            map[x[i]-1][y[i]]=1;
            map[x[i]][y[i]+1]=1;
            map[x[i]][y[i]-1]=1;
        }
    return !map[xx][yy];
}
int solve()
{
    while(head<tail)
    {
        for(int i=0;i<4;i++)
        {
            int nx=xQ[head]+d[0][i],ny=yQ[head]+d[1][i];
            if(nx>=0 && nx<600 && ny>=0 && ny<600 && !book[nx][ny] && check(nx,ny,timeQ[head]+1))
            {
                if(check(nx,ny,1002))
                    return timeQ[head]+1;
                xQ[tail]=nx;
                yQ[tail]=ny;
                timeQ[tail]=timeQ[head]+1;
                book[nx][ny]=1;
                tail++;
            }
        }
        head++;
    }
    return -1;
}

by Andy1262 @ 2021-11-01 13:13:41

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005],b[1005][1005],dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0},ans=2143483647; //数组开大点
int main()
{
/*----------初始化----------*/
    memset(a,127,sizeof(a));
    memset(b,-1,sizeof(b));
    b[0][0]=0;
/*-----------输入-----------*/
    int m;
    cin >> m;
    int x,y,t;
    for(int i=1;i<=m;i++)
    {
        cin >> x >> y >> t;
        for(int j=0;j<=4;j++)
            if(a[x+dx[j]][y+dy[j]]>t) a[x+dx[j]][y+dy[j]]=t;
    }
/*-----------广搜-----------*/
    queue < int > xx;
    queue < int > yy;
    xx.push(0);
    yy.push(0);
    while(!xx.empty())
    {
        int u=xx.front(),v=yy.front();
        xx.pop();
        yy.pop();
        if(a[u][v]==0x7f7f7f7f)
        {
            ans=b[u][v];
            break;
        }
        for(int i=1;i<=4;i++)
        {
            int c=u+dx[i],d=v+dy[i];
            if(c<0 || c>1004 || d<0 ||d>1004) continue;
            if(b[c][d]!=-1) continue;
            if(b[u][v]+1<a[c][d])
            {
                xx.push(c);
                yy.push(d);
                b[c][d]=b[u][v]+1;
            }
        }
    }
/*-----------输出-----------*/
    if(ans==2143483647) cout << -1;
    else cout << ans;
    return 0;
}