112701.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;

bool ok(int y, int x, int a[1000][1000], int n, int m);

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

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;
                cnt++;
            }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;
            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();
                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;
                    }else if (a[ty][tx] == 0 && ok(ty, tx, a, n, m)){
                        a[ty][tx] = 2;
                        cnt++;
                        // cout << tx << " " << ty << "!" << endl;
                        q.push(make_pair(tx, ty));
                    }
                }
                // cout << endl;
            }
            // cout << endl;
        }
    }

    cout << cnt << endl;

    return 0;
}

bool ok(int y, int x, int a[1000][1000], int n, int m){
    // cout << "ok(" << x << "," << y <<  ") : " << endl;
    bool tmp;
    int tx, ty;
    for (int i = 0; i < 8; i += 2){
        tmp = true;
        for (int j = 0; j < 3 && tmp; j++){
            tx = x + modifier2[(i + j) % 8][0];
            ty = y + modifier2[(i + j) % 8][1];
            // cout << tx << " " << ty << endl;
            if (tx < 0 || ty < 0 || tx >= m || ty >= n || a[ty][tx] == 0)
                tmp = false;
        }
        if (tmp)
            // cout << "true\n";
            return true;
            // cout << "fail\n";
    }
    // cout << "false\n";
    return false;
}