Subtask 1

Với mỗi ô ~(i, j)~ là biệt thự, ta tìm tất cả các ô ~(x, y)~ là biệt thự có thể đi đến từ ô ~(i, j)~ bằng BFS.

Độ phức tạp: ~\mathcal{O}((m \cdot n) ^ 2)~

Subtask 2

Gọi:

• ~nc[i][j]~ là ô # gần nhất trên dòng ~i~ về phía bên trái của ô ~(i, j)~.
• ~nv[i][j]~ là ô . gần nhất trên dòng ~i~ về phía bên trái của ô ~(i, j)~.

Xét ô biệt thự ~(i, j)~, với mỗi dòng ~i' \le i~, ta cần tìm trên dòng đó có bao nhiêu ô đến được ~(i, j)~. Với dòng ~i~, các ô biệt thự từ vị trí ~(i, nc[i][j] + 1)~ đến ~(i, j)~ có thể đến được ~(i, j)~. Đối với dòng ~i - 1~, các ô biệt thự từ ~(i - 1, nc[i - 1][nc[i][j] + 1] + 1)~ đến ~(i - 1, nv[i - 1][j])~ sẽ thỏa mãn đến được ~(i, j)~, tương tự với ~i-2, i-3, \dots~

Độ phức tạp: ~\mathcal{O}(m^2 \cdot n)~

Subtask 3

Ta sẽ cải tiến từ subtask 2 bằng các sử dụng hai mảng prefix sum. Để hiểu rõ hơn các bạn có thể tham khảo code ở dưới.

Độ phức tạp: ~\mathcal{O}(m \cdot n)~

Code mẫu

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

const int maxn = 2e3 + 5;

int m, n;
char a[maxn][maxn];
int valid[maxn][maxn];
int nearC[maxn][maxn];
int nearV[maxn][maxn];
int res = 0;


namespace SUB1{
    bool substask_valid(){
        return m <= 50 && n <= 50;
    }

    bool vis[405][405];
    bool valid(int i, int j){
        return i >= 1 && i <= m && j >= 1 && j <= n && a[i][j] == '.';
    }

    int BFS(int i, int j){
        queue<pair<int, int>> qu;
        memset(vis, 0, sizeof(vis));
        qu.push({i, j});
        vis[i][j] = 1;
        int cnt = 0;
        while (qu.size()){
            auto [u, v] = qu.front();
            ++cnt;
            qu.pop();

            if (valid(u + 1, v) && !vis[u + 1][v]){

                vis[u + 1][v] = 1;
                qu.push({u + 1, v});
            }
            if (valid(u, v + 1) && !vis[u][v + 1]){
                vis[u][v + 1] = 1;
                qu.push({u, v + 1});
            }
        }
        return cnt;

    }
    void solve(){

        for (int row = 1; row <= m; row++){
            for (int col = 1; col <= n; col++){
                if (a[row][col] == '#') continue;
                res -= BFS(row, col);
            }
        }
        cout << res << endl;
    }
}

namespace SUB2{
    bool subtask_valid(){
        return m <= 400 && n <= 400;
    }

    const int maxn = 405;

    void solve(){
        for (int row = 1; row <= m; row++){
            for (int col = 1; col <= n; col++){
                if (a[row][col] == '#') continue;
                int insRow = row;
                int l = nearC[row][col] + 1, r = col;
                while (insRow && l <= r){
                    res -= (valid[insRow][r] - valid[insRow][l - 1]);
                    l = nearC[insRow - 1][l] + 1;
                    r = nearV[insRow - 1][r];
                    insRow--;
                }

            }
        }
        cout << res << endl;
    }

}

namespace SUB3{

    int le[maxn][maxn], ri[maxn][maxn];
    void solve(){
        for (int row = 1; row <= m; row++){
            for (int col = 1; col <= n; col++){
                if (a[row][col] == '#') continue;

                int l = nearC[row][col] + 1, r = col;
                le[row][l] = le[row - 1][nearC[row - 1][l] + 1] - valid[row][l - 1]; 
                ri[row][r] = ri[row - 1][nearV[row - 1][r]] + valid[row][r];

                res -= (le[row][l] + ri[row][r]);
            }
        }
        cout << res << endl;
    }
}

void PROGRAM(int _){
    cin >> m >> n;

    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            cin >> a[i][j];
            nearC[i][j] = nearC[i][j - 1];
            nearV[i][j] = nearV[i][j - 1];
            if (a[i][j] == '#') nearC[i][j] = j;
            if (a[i][j] == '.') nearV[i][j] = j;

            valid[i][j] = valid[i][j - 1] + (a[i][j] == '.');
            res += (a[i][j] == '.');
        }
    }

    res = res * (res + 1) / 2;    
    SUB3::solve();


}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;
    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}