boom.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

#define MAXN 1010

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int N, R;
int color[MAXN][MAXN];
string A[MAXN];

vector<int> coverers[MAXN][MAXN];
map<vector<int>, int> sums;

void subset_add(const vector<int>& S, int val) {
  int N = S.size();
  for (int i = 0; i < 1 << N; i++) {
    vector<int> V;
    for (int j = 0; j < N; j++) {
      if (i & 1 << j) {
        V.push_back(S[j]);
      }
    }
    ++sums[V];
  }
}

void dfs(int r, int c, int col) {
  if (color[r][c] != -1) {
    return;
  }
  color[r][c] = col;
  for (int i = 0; i < 4; i++) {
    int nr = r;
    int nc = c;
    for (int j = 0; j < R; j++) {
      nr += dr[i];
      nc += dc[i];
      if (nr < 0 || nr >= N || nc < 0 || nc >= N ||
          A[nr][nc] == '#') {
        break;
      } else if (A[nr][nc] == '*') {
        dfs(nr, nc, col);
        break;
      }
    }
  }
}

int main() {
  cin >> N >> R;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  int comps = 0;
  memset(color, -1, sizeof(color));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (A[i][j] != '*' || color[i][j] != -1) {
        continue;
      }
      dfs(i, j, comps++);
    }
  }
  for (int r = 0; r < N; r++) {
    for (int c = 0; c < N; c++) {
      if (A[r][c] != 'S' && A[r][c] != '.') {
        continue;
      }

      vector<int>& comps = coverers[r][c];
      for (int i = 0; i < 4; i++) {
        int nr = r;
        int nc = c;
        for (int j = 0; j < R; j++) {
          nr += dr[i];
          nc += dc[i];
          if (nr < 0 || nr >= N || nc < 0 || nc >= N ||
              A[nr][nc] == '#') {
            break;
          } else if (A[nr][nc] == '*') {
            comps.push_back(color[nr][nc]);
            break;
          }
        }
      }
      sort(comps.begin(), comps.end());
      comps.resize(unique(comps.begin(), comps.end()) - comps.begin());
      if (A[r][c] == 'S') {
        subset_add(comps, 1);
      }
    }
  }

  int result = 0;
  int total_stumps = sums[vector<int>()];
  for (int r = 0; r < N; r++) {
    for (int c = 0; c < N; c++) {
      if (A[r][c] != '.') {
        continue;
      }
      const vector<int>& comps = coverers[r][c];

      int stumps = 0;
      for (int i = 1; i < 1 << comps.size(); i++) {
        vector<int> v;
        for (int j = 0; j < comps.size(); j++) {
          if (i & 1 << j) {
            v.push_back(comps[j]);
          }
        }
        auto it = sums.find(v);
        if (it != sums.end()) {
          stumps += (__builtin_popcount(i) % 2 ? 1 : -1) * it->second;
        }
      }
      for (int i = 0; i < 4; i++) {
        int nr = r;
        int nc = c;
        for (int j = 0; j < R; j++) {
          nr += dr[i];
          nc += dc[i];
          if (nr < 0 || nr >= N || nc < 0 || nc >= N ||
              A[nr][nc] == '#') {
            break;
          } else if (A[nr][nc] == 'S') {
            bool counted = false;
            for (int k : comps) {
              if (binary_search(coverers[nr][nc].begin(),
                                coverers[nr][nc].end(), k)) {
                counted = true;
                break;
              }
            }
            if (!counted) {
              stumps++;
            }
          }
        }
      }
      if (stumps == total_stumps) {
        ++result;
      }
    }
  }

  cout << result << endl;
}