admin管理员组文章数量:1529452
Codeforces Round #689 (Div. 2, based on Zed Code Competition):1461B Find the Spruce
题目:
Holidays are coming up really soon. Rick realized that it’s time to think about buying a traditional spruce tree. But Rick doesn’t want real trees to get hurt so he decided to find some in an 𝑛×𝑚 matrix consisting of “*” and “.”.
To find every spruce first let’s define what a spruce in the matrix is. A set of matrix cells is called a spruce of height 𝑘 with origin at point (𝑥,𝑦)
if:
All cells in the set contain an "*".
For each 1≤𝑖≤𝑘 all cells with the row number 𝑥+𝑖−1 and columns in range [𝑦−𝑖+1,𝑦+𝑖−1]
must be a part of the set. All other cells cannot belong to the set.
Examples of correct and incorrect spruce trees:
Now Rick wants to know how many spruces his 𝑛×𝑚 matrix contains. Help Rick solve this problem.
输入:
Each test contains one or more test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤10).
The first line of each test case contains two integers 𝑛 and 𝑚 (1≤𝑛,𝑚≤500) — matrix size.
Next 𝑛 lines of each test case contain 𝑚 characters 𝑐𝑖,𝑗 — matrix contents. It is guaranteed that 𝑐𝑖,𝑗 is either a “.” or an “*”.
It is guaranteed that the sum of 𝑛⋅𝑚 over all test cases does not exceed 5002 (∑𝑛⋅𝑚≤5002).
输出:
For each test case, print single integer — the total number of spruces in the matrix.
例子:
Input:
4
2 3
.*.
***
2 3
.*.
**.
4 5
.***.
*****
*****
*.*.*
5 7
..*.*..
.*****.
*******
.*****.
..*.*..
Output:
5
3
23
34
解答:
可以感觉到较为简单的算法就是把每一个节点下的树都加起来,就是总树。
那么怎么加呢,肯定是从下往上加,因为上面的节点需要下面的数据,那么现在要考虑的就是如何计算每一个节点的树的个数。
除了自身外,需要考虑它的下一行的三个元素的情况。仔细思考一下,会发现该节点除自身外的树的个数为下一行三个元素包括自身以他们为顶点的树的个数的最小值。因为少一个完整的子树,以最上面的点为顶点的树就不会完整。
因此凭借这个算法,得到以下AC代码,注意数组越界的情况,要进行排除。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
long long ans = 0;
int n, m;
int sum[501][501] = {0};
cin>>n>>m;
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
char temp;
cin>>temp;
if(temp == '*')
{
sum[i][j] = 1;
}
else
{
sum[i][j] = 0;
}
}
}
for(int i = n-1 ;i >= 0;i--)
{
for(int j = 0;j < m;j++)
{
if(sum[i][j] == 1)
{
int minn = 1.0E6;
ans++;
if(i + 1 >= n || j - 1 < 0 || j + 1 >= m)
{
continue;
}
for(int p = j - 1;p <= j + 1;p++)
{
minn = min(minn, sum[i+1][p]);
}
sum[i][j] += minn;
ans += minn;
}
}
}
cout<<ans<<endl;
}
return 0;
}
本文标签: BasedZedDivcodeforcesFind
版权声明:本文标题:CodeforcesRound #689 (Div. 2, based on Zed Code Competition):1461B Find the Spruce 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1726694240a1081022.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论