112701_2.cpp

#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long int lli;
typedef queue<int> qi;
typedef queue<pii> qii;

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

int main(){

    int n, m, a[1000][1000], cnt = 0, tx, ty, x1, y1;
    char tmpc;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++){
            scanf("%c", &tmpc);
            if (tmpc == '#')
                a[i][j] = 1;
            else if (tmpc == '.')
                a[i][j] = 0;
            else
                j--;
        }

    for (int y = 0; y < n; y++){
        for (int x = 0; x < m; x++){
            if (a[y][x] != 1)
                continue;
            int maxx = -1, minx = 1001, maxy = -1, miny = 1001;
            qii q;
            q.push(make_pair(x, y));
            while (q.size()){
                x1 = q.front().first;
                y1 = q.front().second;
                // cout << x1 << " " << y1 << ":" << endl;
                a[y1][x1] = 2;
                q.pop();
                if (x1 > maxx)
                    maxx = x1;
                if (x1 < minx)
                    minx = x1;
                if (y1 > maxy)
                    maxy = y1;
                if (y1 < miny)
                    miny = y1;
                int tx, ty;
                for (int i = 0; i < 4; i++){
                    tx = x1 + modifier[i][0];
                    ty = y1 + modifier[i][1];
                    // cout << tx << " " << ty << ", ";
                    if (tx < 0 || ty < 0 || tx >= m || ty >= n)
                        continue;
                    if (a[ty][tx] == 1){
                        q.push(make_pair(tx, ty));
                        a[ty][tx] = 2;
                    }
                }
            }
            cnt += (maxx - minx + 1) * (maxy - miny + 1);
        }
    }

    cout << cnt << endl;

    return 0;
}