598D - Igor In the Museum - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int x,y;
vector<vector<char>>c;
vector<vector<bool>>vis;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

vector<vector<pair<int,int>>>parent;
pair<int,int> find(pair<int,int>g){
    if(parent[g.first][g.second]==g)
        return g;
    return find(parent[g.first][g.second]);
}
void Union(int i,int j,int ii,int jj){
    parent[ii][jj]= find({i,j});
}
void fill(){
   for(int i = 0;i < x;i++)
        for(int j = 0 ; j < y;j++)
        parent[i][j] = {i,j};
}

bool isvalid(int xx,int yy){
    return xx >= 0 and yy >= 0 and xx < x and yy < y;
}

int dfs(int xx,int yy){
    if(c[xx][yy] == '*') return 1;
    vis[xx][yy] = 1;
    int cnt = 0;
    for(int i = 0 ; i < 4;i++){
        if(isvalid(xx + dx[i],yy + dy[i]) && !vis[xx + dx[i]][yy + dy[i]]){
            Union(xx,yy,xx + dx[i],yy + dy[i]);
           cnt += dfs(xx + dx[i],yy + dy[i]);
        }
    }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false); 
        cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt" , "r", stdin );
        freopen("out.txt", "w", stdout);
    #endif
    int m; cin>>x>>y>>m;
    c.resize(x,vector<char>(y));
    parent.resize(x,vector<pair<int,int>>(y));
    vis.resize(x,vector<bool>(y));
    fill();
    map<pair<int,int>,int>mp;
    for(int i = 0 ; i < x;i++)
        for(int j = 0 ; j < y;j++)
            cin>>c[i][j];
    
    for(int i = 0 ; i < m;i++){
        int a,b; cin>>a>>b;
        a--; b--;
        pair<int,int> it = find({a,b});
        if(mp.find(it) != mp.end()) cout<<mp[it]<<'\n';
        else{
             mp[{it.first,it.second}] = dfs(a,b);
             cout<<mp[{it.first,it.second}]<<'\n';
        }
    }
     
}