B. Find the Spruce

B. Find the

题意

给你一个n×m的矩阵，每个位置都有一个’‘或者’.‘，现在定义一个目标图案，如下图：

只有类似上面的这种才行，现在问你给你的n×m的矩阵中，有多少个这样的图案。

思路

dp

我们设一个二维数组dp[i][j]，表示以(i,j)这个结尾有多少个连续的’‘。然后我们可以以任何一个(i,j)为’‘的位置开始找，那么我们可以直接遍历一遍图，我们观察上面的图可以发现满足条件的规律，我们假设最上面的哪一个单独的位置的坐标为(i, j)，那么如果有第二层，那么第二层最左边的坐标为(i+1, j-1)，如果有第三层，那么第三层最左边的哪一个的坐标为(i + 2, j -2)，那么我们发现下一层的最左边的那也个的坐标就是(i+层,j-层数)，那么我们可以直接从这个下一层的最左边这个位置开始找，看以这个位置开始的’‘的个数是否满足条件，对于第一层，它的’*'的个数是1，第二层是3，第三层是5，那么就是满足1 + 2 * tag（tag表示层数）。

#include using namespace std;const int N = 510;int n, m, ans;
int mp[N][N];
int f[N][N];void check(int x, int y)
{int tag