[Codeforces] Codeforces Round #689 (Div. 2) B. Find the Spruce
問題
方針
高さが \( k \) の木を作れるかどうかは、連続する '*’ の数が分かればいいので、連続する '*’ を累積和を用いて数えます。あるマスから下に向かって順番に高さ \( k \) の木が作れるかを見ていけば良いです。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m; string c[500]; void solve() { int a[n][m + 1]{}; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (c[i][j] == '*') { a[i][j + 1] = a[i][j] + 1; } else { a[i][j + 1] = 0; } } } ll sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (c[i][j] == '.') continue; sum++; for (int k = 1; i + k < n; k++) { if (j - k < 0 || j + k + 1 > m) break; if (c[i + k][j] == '.') break; int l = a[i + k][j] - a[i + k][j - k]; int r = a[i + k][j + k + 1] - a[i + k][j + 1]; if (l == k && r == k) { sum++; } else { break; } } } } cout << sum << "\n"; } int main() { int t; cin >> t; while (t--) { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> c[i]; } solve(); } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません