Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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[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;
- a[y1][x1] = 2;
- q.pop();
- int tx, ty;
- for (int i = 0; i < 8; i++){
- tx = x1 + modifier[i][0];
- ty = y1 + modifier[i][1];
- 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++;
- q.push(make_pair(tx, ty));
- }
- }
- }
- }
- }
- cout << cnt << endl;
- return 0;
- }
- bool ok(int y, int x, int a[1000][1000], int n, int m){
- 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 + modifier[(i + j) % 8][0];
- ty = y + modifier[(i + j) % 8][1];
- if (tx < 0 || ty < 0 || tx >= m || ty >= n || a[ty][tx] == 0)
- tmp = false;
- }
- if (tmp)
- return true;
- }
- return false;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement