【Codeforces 598D】Igor In the Museum

【链接】 我是链接,点我呀:)

【题意】

题意

【题解】

同一个联通块里面答案都一样。
把每个联通块的答案都算出来 然后赋值就好

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

int n,m,k;

int dx[4] = {0,0,1,-1};

int dy[4] = {1,-1,0,0};

char s[N+10][N+10];

bool bo[N+10][N+10];

int ans[N+10][N+10];

pair<int,int> dl[N*N+10];

int head,tail;

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> m >> k;

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

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

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

            if (!bo[i][j] && s[i][j]=='.'){

                head = 1,tail = 1;

                dl[head] = {i,j};

                int cnt = 0;

                bo[i][j] = true;

                while (head<=tail){

                    int x = dl[head].first,y = dl[head].second;

                    head++;

                    for (int l = 0;l < 4;l++){

                        int tx = x + dx[l],ty = y + dy[l];

                        if (tx>=1 && tx <= n && ty>=1 && ty<=m){

                            if (!bo[tx][ty] && s[tx][ty]=='.'){

                                bo[tx][ty] = true;

                                tail++;

                                dl[tail].first = tx;

                                dl[tail].second = ty;

                            }else if (s[tx][ty]=='*'){

                                cnt++;

                            }

                        }

                    }

                }

                for (int i = 1;i <= tail;i++){

                    ans[dl[i].first][dl[i].second] = cnt;

                }

            }

    for (int i = 1;i <= k;i++){

        int x,y;

        cin >> x >> y;

        cout<<ans[x][y]<<endl;

    }

	return 0;

}