Codeforces 847I - Noise Level

847I - Noise Level

思路：bfs。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=;

char mp[N][N];

ll dp[N][N]={};

bool vis[N][N]={false};

int n,m,q,p;

int dir[][]={,,,,,-,-,};

struct node

{

    int x,y,v;

};

vector<node>s;

void bfs(int x,int y,int v)

{

    node now,next;

    queue<node>q;

    now.x=x;

    now.y=y;

    now.v=v;

    q.push(now);

    while(q.size())

    {

        now=q.front();

        dp[now.x][now.y]+=now.v;

        q.pop();

        for(int i=;i<;i++)

        {

            next.x=now.x+dir[i][];

            next.y=now.y+dir[i][];

            next.v=now.v/;

            if(<=next.x&&next.x<n&&<=next.y&&next.y<m&&mp[next.x][next.y]!='*'&&vis[next.x][next.y]==false&&next.v!=)//判断一下值是不是0可以优化很多

            {

                vis[next.x][next.y]=true;

                q.push(next);

            }

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    cin>>n>>m>>q>>p;

    for(int i=;i<n;i++)cin>>mp[i];

    for(int i=;i<n;i++)

        for(int j=;j<m;j++)

            if(isalpha(mp[i][j]))

                s.pb(node{i,j,(mp[i][j]-'A'+)*q});

    for(int i=;i<s.size();i++)

    {

        vis[s[i].x][s[i].y]=true;

        bfs(s[i].x,s[i].y,s[i].v);

        mem(vis,false);

    }

    int res=;

    for(int i=;i<n;i++)

        for(int j=;j<m;j++)

            if(dp[i][j]>p)res++;

    cout<<res<<endl;

    return ;

}