P1332 血色先锋队 题解

DGL__DGL · 2024-05-10 21:15:14 · 个人记录

传送门

动规暴力过的

思路:用每个点更新它上下左右的四个点,当一个点第一次被更新的时间就是它被感染的时间。

把第一批感染者设为 0 ，其他设为正无穷，用 min 更新即可。

由题目易知，最多循环 1000 次就可保证每个点都被更新。

代码（莫抄）

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
int x,y;
int res=1000;
int t[514][514];

int mian()
{
    memset(t,0x3f,sizeof t);
    cin>>n>>m>>a>>b;
    for(int i=1;i<=a;i++)
  {
    cin>>x>>y;
    t[x][y]=0;
    }
    while(res--)
      for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            t[i+1][j]=min(t[i+1][j],t[i][j]+1);
            t[i][j+1]=min(t[i][j+1],t[i][j]+1);
            t[i-1][j]=min(t[i-1][j],t[i][j]+1);
          t[i][j-1]=min(t[i][j-1],t[i][j]+1);
        }
    for(int i=1;i<=b;i++)
    {
        cin>>x>>y;
        cout<<t[x][y]<<'\n';
    }



    return 0;
 } 

时间复杂度分析

预处理：O（500 \times 500 \times 1000=2.5 \times 10^8）

查询： O（b）

然而洛谷一秒可以跑 2e9 次运算。

发现对于预处理，时间主要花费在min运算上，所以开O2优化即可。

只需 300ms 左右即可处理完。