[AOJ] No. 0632 休憩スペース (Refreshment Area)

2019年7月2日

問題

方針

縦方向と横方向に分けて考える

休憩スペースは南北方向または東西方向に置くことが可能なので、縦方向と横方向に分けて考えます。

連続する空マスを数える

ある方向に向かって連続する空マスを数え、その値が \( D \) よりも大きい時、そのマスを末端として休憩スペースを置くことができます。つまり、休憩スペースの末端を調べることで休憩スペースを設けるパターンの場合の数が分かります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M, D;
  cin >> N >> M >> D;
  char c[N][M];
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < M; j++) {
      c[i][j] = s[j];
    }
  }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int cnt = 0;
    for (int j = 0; j < M; j++) {
      if (c[i][j] == '.') cnt++;
      else cnt = 0;
      if (cnt >= D) ans++;
    }
  }
  for (int i = 0; i < M; i++) {
    int cnt = 0;
    for (int j = 0; j < N; j++) {
      if (c[j][i] == '.') cnt++;
      else cnt = 0;
      if (cnt >= D) ans++;
    }
  }
  cout << ans << "\n";
  return 0;
}