Türkçe

Eğer verilen ızgarayı, ızgaradaki alanların node olduğu bir graph olarak düşünürsek her odadaki duvar sayısını graph search algoritmalarından biri (çözümdeki algoritma DFS) ile bulabiliriz. Sonuç olarak toplam \(O(\mathbf{X \cdot Y})\) sürede tüm odalardaki duvar sayılarını bulup odaların içindeki alanlara bu odaları eşleştirebiliriz.

Bundan sonraki yapacağımız tek şey boyacıların bulundukları konumlarda kaç tane duvar olduğunu bulmak. Bunu da \(O(\mathbf{K})\) sürede bulabiliriz.

English

We can think of the given grid as a graph such that every cell of the grid will correspond to a graph node. To find the number of walls in every room we can use a graph search algorithm (DFS in the solution). The number of walls in every room is found mapped to the cells in that room in a total of \(O(\mathbf{X \cdot Y})\) time.

Now, all we have to do is to find how many walls are there to paint for each painter. We can do that at \(O(\mathbf{K})\) time

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

vector<string> grid;
int A[1 << 10][1 << 10];

int dfs(int r, int c, int a)
{
    if(A[r][c] == a) return 0;
    A[r][c] = a;
    int res = 0;
    for(int rr = r-1; rr <= r+1; ++rr)
        for(int cc = c-1; cc <= c+1; ++cc)
            if(abs(rr-r) + abs(cc-c) == 1)
            {
                if(grid[rr][cc] != '.') ++res;
                else res += dfs(rr, cc, a);
            }

    return res;
}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    grid.resize(n);
    for(int i = 0; i < n; ++i) cin >> grid[i];

    vector<int> rooms;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(grid[i][j] == '.' && A[i][j] == 0)
                rooms.push_back(dfs(i, j, rooms.size() + 1));

    for(int i = 0; i < k; ++i)
    {
        int r, c;
        cin >> r >> c;
        --r;
        --c;
        cout << rooms[A[r][c] - 1] << endl;
    }
}