B. Find the Spruce(暴力)

B. Find the Spruce(暴力)

题目

思路：先预处理一下每个元素之后会有多少个连续的’*’,时间O(n^3），然后对于每一个元素暴力模拟一下，时间O
(n^3)，细节见代码。

Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<bitset>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;
int lst[505][505];
int Mod = 1e9 + 7;
int n, m;ll sum = 0;
int dp[505][505];void check(int x,int y)
{int g = 0;int f = 0;while (1){if (x + g > n || y + g > m||y-g<1)break;if ( dp[x+g][y-g]<1+2*g)f = 1;g++;if (f)break;sum++;}
}int main()
{FAST;int t;cin >> t;while (t--){cin >> n >> m;for (int i = 1;i <= n;i++){for (int j = 1;j <= m;j++){char g;cin >> g;if (g == '*')lst[i][j] = 1;else lst[i][j] = 0;}}sum = 0;memset(dp, 0, sizeof(dp));for (int i = 1;i <= n;i++){for (int j = 1;j <= m;j++){int su = 0;for (int k = j;k <= m;k++){if (lst[i][k] == 1)su++;else break;}dp[i][j] = su;}}for (int i = 1;i <= n;i++){for (int j = 1;j <= m;j++){if (lst[i][j])check(i, j);}}cout << sum << endl;}
}