CodeForces 598D Igor In the Museum

暴力DFS预处理答案

#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;

const int maxn=1000+10;
char s[maxn][maxn];
struct X
{
    int x,y;
    X(int a,int b)
    {
        x=a;
        y=b;
    }
};
queue<X>Q;
int n,m,k;
bool flag[maxn][maxn];
int ans[maxn][maxn];
int dir[4][2]={
    {1,0},
    {-1,0},
    {0,-1},
    {0,1}
};

bool P(int a,int b)
{
    if(a>=0&&a<n&&b>=0&&b<m&&s[a][b]=='.') return 1;
    return 0;
}

int tot;

int check(int a,int b)
{
    int res=0;

    if(a-1>=0&&a-1<n&&b>=0&&b<m&&s[a-1][b]=='*') res++;
    if(a+1>=0&&a+1<n&&b>=0&&b<m&&s[a+1][b]=='*') res++;
    if(a>=0&&a<n&&b-1>=0&&b-1<m&&s[a][b-1]=='*') res++;
    if(a>=0&&a<n&&b+1>=0&&b+1<m&&s[a][b+1]=='*') res++;

    return res;
}

void dfs(int a,int b)
{
    flag[a][b]=1;

    Q.push(X(a,b));

    tot=tot+check(a,b);

    for(int i=0;i<4;i++)
    {
        int ta=a+dir[i][0];
        int tb=b+dir[i][1];
        if(P(ta,tb)==0) continue;
        if(flag[ta][tb]==1) continue;
        dfs(ta,tb);
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++) scanf("%s",s[i]);

    memset(flag,0,sizeof flag);
    memset(ans,0,sizeof ans);

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(s[i][j]=='*') continue;
            tot=0;
            if(flag[i][j]==1) continue;

            dfs(i,j);
            while(!Q.empty()){
                ans[Q.front().x][Q.front().y]=tot;
                Q.pop();
            }
        }
    }

    for(int i=1;i<=k;i++)
    {
        int tx,ty; scanf("%d%d",&tx,&ty);
        printf("%d
",ans[tx-1][ty-1]);
    }

    return 0;
}