CFR Educational 1 D. Igor In the Museum ( Easy BFS )

Problem - D - Codeforces
Simply simulating will be alright.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;
const int MAXM = 1e3 + 3;
const int MAXK = 1e6 + 6;

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

int n, m, k;
char G[ MAXN ][ MAXM ];

int cc[ MAXN ][ MAXM ], cc_cnt;
int ans[ MAXN * MAXM ];

void bfs(int sx, int sy){
    queue<int> que;
    que.push( sx * MAXM + sy );
    cc[ sx ][ sy ] = cc_cnt;
    while( !que.empty() ){
        int x = que.front() / MAXM;
        int y = que.front() % MAXM;
        que.pop();
        for(int d = 0; d < 4; ++d){
            int nx = x + dx[ d ];
            int ny = y + dy[ d ];
            if( nx < 0 || ny < 0 || nx >= n || ny >= m ) continue;
            if( G[ nx ][ ny ] == '.' ){
                if( cc[ nx ][ ny ] ) continue;
                cc[ nx ][ ny ] = cc_cnt;
                que.push( nx * MAXM + ny );
            }
            if( G[ nx ][ ny ] == '*' )
                ++ans[ cc_cnt ];
        }
    }
}

void solve(){
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if( G[ i ][ j ] == '.' && !cc[ i ][ j ] ){
                ++cc_cnt;
                bfs( i, j );
            }
    while( k-- ){
        int x, y; scanf("%d%d", &x, &y);
        printf("%d\n", ans[ cc[ --x ][ --y ] ]);
    }
}

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