C - 菱型カウント 〜ABC021〜

問題

C - 菱型カウント

感想

やるだけではあると思うのですが，実装が重いのでめんどくさかったです。 こういう問題苦手。自分はプログラミングが向いてないなと実感する問題ですね笑.....

考え

(i, j) 点に関して全探索をする。そして，上下左右に Kの幅を伸ばして白であるか確かめる必要が あります。この時に上下左右の両方（二方向）で K について全探索すると となり TLE となるので，片方の方向だけ全探索をして，もう片方は部分和を使って全探索を省く必要があるでしょう。

Accepted Program

#include <iostream>
using namespace std;
#define ll long long

int main () {
  int h, w, k;
  cin >> h >> w >> k;
  string str[h];
  for (int i = 0; i < h; i++) {
    cin >> str[i];  
  }
  ll ans = 0;
  ll sum[h][w];
  for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
      sum[i][j] = 0;
      if (j == 0) {
        if (str[i][j] == 'x') {
          sum[i][j] = -1;  
        }  
        if (str[i][j] == 'o') {
          sum[i][j] = 0;  
        }
      }  
      else {
        if (str[i][j] == 'x') {
          sum[i][j] = sum[i][j - 1] - 1;  
        }  
        if (str[i][j] == 'o') {
          sum[i][j] = sum[i][j - 1];  
        }
      }
    }  
  }
  for (int i = k - 1; i <= h - k; i++) {
    for (int j = k - 1; j <= w - k; j++) {
      for (int l = 0; l < k; l++) {
        if (l == k - 1) {
          if (str[i - l][j] != 'o' || str[i + l][j] != 'o') {
            break; 
          }  
        }
        else {
          int yoko = k - l - 1;
          if (j - yoko == 0) {
            if (sum[i - l][j + yoko] != 0) {
              break;
            }  
            if (sum[i + l][j + yoko] != 0) {
              break;
            }
          }  
          else {
            if (sum[i - l][j + yoko] - sum[i - l][j - yoko - 1] != 0) {
              break;
            }  
            if (sum[i + l][j + yoko] - sum[i + l][j - yoko - 1] != 0) {
              break; 
            }
          }
        }
        if (l == k - 1) {
          ans++;  
        }
      }         
    }  
  }
  cout << ans << endl;
}