【題解】Codeforces 1461B. Find the Spruce

【題目敘述】https://codeforces.com/contest/1461/problem/B

#include <bits/stdc++.h>
using namespace std;
 
int t, n, m;
string s;
 
int main(){
    cin >> t;
    while (t--){
        cin >> n >> m;
        int g[n+2][m+2] = {}, dp[n+2][m+2] = {}, ans = 0;
        for (int i = 1; i <= n; i++){
            cin >> s;
            for (int j = 1; j <= m; j++){
                if (s[j-1] == '*') g[i][j] = 1;
                else g[i][j] = 0;
            }
        }
        for (int i = n; i >= 1; i--){
            for (int j = 1; j <= m; j++){
                if (!g[i][j]) continue;
                dp[i][j] = min({dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]})+1;
                ans += dp[i][j];
            }
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends