AT_abc383_c 题解

ikunTLE · 2024-12-08 11:23:58 · 题解

题目传送门

思路

本题可以使用记忆化搜索。

定义二维数组 f，f_{i,j} 表示从 (i,j) 点出发到最近加湿器的距离。首先用 \infty 将 f 填充，以每个加湿器为起点作 bfs。当到达 (i,j) 点时，若其距离小于 f_{i,j}，则继续 bfs；否则在这个点终止，因为再以这点继续遍历，其剩余可走的长度必定不如之前的长。bfs 需记录其走过的长度 L，当 L=D 时终止当前点的 bfs。最后统计不为 \infty 的点的数量即可。

如果不做记忆化，那么最差情况下，以每一个加湿器都会遍历整个网格，时间复杂度为 \mathcal{O}(N^4)。做了记忆化以后，不存在所有的点都会被走过的情况，时间复杂度约为 \mathcal{O}(N^3)，且常数非常小，实测时间不会超过 400 毫秒，可以通过此题。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e3+10;
char s[N][N];
struct node{
    int x,y,step;
};queue<node>q;
int h,w,d,f[N][N];
int dx[]={0,-1,1,0,0},dy[]={0,0,0,-1,1};
void bfs(int sx,int sy){
    while(!q.empty())
        q.pop();
    q.push({sx,sy,0});
    while(!q.empty()){
        node u=q.front();q.pop();
        int x=u.x,y=u.y,step=u.step;
        if(step>=d)
            continue;
        for(int i=1;i<=4;++i){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=1&&xx<=h&&yy>=1&&yy<=w&&s[xx][yy]!='#'&&f[x][y]+1<f[xx][yy]){
                f[xx][yy]=f[x][y]+1;
                q.push({xx,yy,step+1});
            }
        }
    }
    return;
}
signed main(){
    h=read(),w=read(),d=read();
    for(int i=1;i<=h;++i)
        scanf("%s",s[i]+1);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=h;++i)
        for(int j=1;j<=w;++j)
            if(s[i][j]=='H')
                f[i][j]=0;
    for(int i=1;i<=h;++i)
        for(int j=1;j<=w;++j)
            if(s[i][j]=='H')
                bfs(i,j);
    int sum=0;
    for(int i=1;i<=h;++i)
        for(int j=1;j<=w;++j)
            sum+=(f[i][j]<N*N);
    printf("%lld\n",sum);
    return 0;
}