样例没过,求调

P2895 [USACO08FEB] Meteor Shower S

wq_pw @ 2024-01-02 20:35:53

/*(^v^)*/
#include<bits/stdc++.h>
using namespace std;
const int N=305,M=50000;
int dx[]={ 1, 0, 0,-1};
int dy[]={ 0, 1,-1, 0};
int n,m,T=1e9;
struct mp{int mt,tm,pt;}a[N][N];
void dfs(int x,int y,int t)
{
    t++;
    if(a[x][y].mt==0)
    {
        T=min(T,t);
        return ;
    }
    if(a[x][y].tm<=t || x<0 || y<0 || a[x][y].pt==1)  return ;
    for(int i=0;i<4;i++)
    {
        a[x][y].pt=1;
        dfs(x+dx[i],y+dy[i],t);
    }
}

signed main()
{
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,t;  cin>>x>>y>>t;
        a[x][y].tm=t;a[x][y].mt=1;
    }
    dfs(0,0,0);
    if(T==1e9)  cout<<"-1";
    else cout<<T;
    return 0;
}
/*(^v^)*/

by 13288917088c @ 2024-01-04 13:09:11

输入流星数据那里错了。

建议把a数组的tm初始化为inf(就是0x7fffffff),然后每次对a[x][y].tm,a[x+1][y].tm,a[x-1][y].tm,a[x][y+1].tm,a[x][y-1].tm对t取min,然后执行a[x][y].mt=a[x+1][y].mt=a[x-1][y].mt=a[x][y+1].mt=a[x][y-1].mt=1;

其他应该都没问题了。


|