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;
	}
}