大一acmer日常记录day23:bfs最短时间 快速线性筛

大一acmer日常记录day23:bfs最短时间 快速线性筛,第1张

大一acmer日常记录day23:bfs最短时间 快速线性筛 洛谷p2895:bfs

# include 
using namespace std;
struct node
{
    int x;
    int y;
    int time;
}p;
int mp[305][305],vis[305][305];//陨石掉落时间地图,访问标记地图
int m,nx,ny,t;
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};//方向数组
queueq;
void bfs()
{
    vis[0][0]=1;
    p.x=0,p.y=0,p.time=0;
    q.push(p);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        for(int i=0;i<4;i++)//四个方向
        {
            node tem;//临时结构体
            tem.x=p.x+dx[i];
            tem.y=p.y+dy[i];
            tem.time=p.time+1;
            if(tem.x<0||tem.y<0||tem.time>=mp[tem.x][tem.y]||vis[tem.x][tem.y]==1)continue;//判断所有边界情况



                if(mp[tem.x][tem.y]==9999)//当值为9999,证明陨石无法波及到该点,bfs结束
                {
                    cout<>m;
    for(int i=1;i<=m;i++)
    {
        cin>>nx>>ny>>t;
        mp[nx][ny]=min(t,mp[nx][ny]);//取陨石最早波及的时间
        for(int j=0;j<4;j++)
        {
           int tx=nx+dx[j],ty=ny+dy[j];
           if(tx>=0&&ty>=0)//注意边界,不然re
           {
               mp[tx][ty]=min(t,mp[tx][ty]);//取陨石最早波及的时间
           }
        }
    }
    bfs();
    return 0;
}

快速线性筛:

# include 
using namespace std;
bool num[30000000];//所有数字
long long prime[9000000];//保存素数
int main ()
{
    long long cnt=0,n;
    cin>>n;
    memset(num,1,sizeof(num));//假设素数为1
    num[0]=num[1]=0;//合数为0
    for(long long i=2;i<=n;i++)
    {
        if(num[i])
            prime[cnt++]=i;
        for(long long j=0;j 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5718890.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存