ABC018 C - 菱型カウント
問題
考察
$ (i,j)を大きさ$ Kの菱形に塗れる場合というのは、以下をすべて満たす場合。
$ (i-1,j)を大きさ$ K - 1で菱形に塗れる
$ (i+1,j)を大きさ$ K - 1で菱形に塗れる
$ (i,j-1)を大きさ$ K - 1で菱形に塗れる
$ (i,j+1)を大きさ$ K - 1で菱形に塗れる
なので各マスについて大きさ1から調べていけば$ O(RCK)
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int main() {
int R, C, K;
cin >> R >> C >> K;
vector<vector<int>> grid(R, vector<int>(C, 0));
rep(i, R) rep(j, C) {
char c;
cin >> c;
}
auto good = &(int i, int j, int k) { if (gridij == 0) return false; if (i - 1 < 0 || gridi - 1j < k - 1) return false; if (i + 1 >= R || gridi + 1j < k - 1) return false; if (j - 1 < 0 || gridij - 1 < k - 1) return false; if (j + 1 >= C || gridij + 1 < k - 1) return false; return true;
};
for (int k = 2; k <= K; ++k) {
rep(i, R) rep(j, C) {
if (good(i, j, k)) gridij = k; }
}
int ans = 0;
rep(i, R) rep(j, C) ans += (gridij == K); cout << ans << endl;
return 0;
}