P8325 [COCI2021-2022#5] Dijamant 题解

_Birdly_ · 2022-07-08 22:47:46 · 题解

这道题前前后后花了我很长时间 14个小时，用了很多思路，bfs，dfs，爆搜，最后不是 RE 就是 TLE。最后仔细观察了一下菱形，认为模拟就可以直接做，然后恍然大悟。

题目描述

题目就是给定个二维数组，求出上面有多少个菱形，且这个菱形需要是合法的。怎么判定它是不是合法的？

1.菱形的每条边都需要由 # 构成。

2.菱形的内部只能由 . 填充。

3.由 样例3 我们可以知道，不同菱形的点是可以重合的。

判定菱形

因为题目中不同边长的菱形其实是相似的，所以就有了一下思路：

先找到菱形最高点的坐标，而后找到最低点的坐标。

因为菱形可以看做两个全等的等腰三角形在底上拼合而成，

所以两三角形的底，即是菱形的一条对称轴。

于是我们从菱形上面的三角形的每一个点开始遍历：

如果点在边上而且字符为 . ，那么这个菱形就不是合法的；

相同，当点不在菱形边上而且字符为 # ，那么这个菱形也不是合法的。

变量声明

将菱形最高点的 x 坐标记作 Ux，将菱形最高点的 y 坐标记作 Uy。

将菱形最低点的 x 坐标记作 Dx，将菱形最低点的 y 坐标记作 Dy。

将两三角形的底所在的 x 坐标记作 Mx。

将两三角形的顶点的距离记作 H。

将菱形之上的三角形第 i 行的点的数量记作 PN_i。

寻找变量

输入后遍历数组，当遇到 # 时，赋值 Ux = i_1，Uy = j_1。

从 Dx 和 Dy 的坐标向下搜，搜到 # 为止，赋值 Dx = i_2，Dy = j_2。

关于 Mx:

如何遍历菱形上下两个三角形

如下图，是一个菱形上方的三角形以及每行的点的数量：

由此可见，在第 n 行时：

如下图，是一个菱形下方的三角形以及每行的点的数量：

可以看到，下方的三角形其实就是上方三角形倒立过来。

所以我们只需要用一个双层循环，就可以遍历整个菱形！

Code Time

说了这么多，到了大家最喜欢的代码啦！

#include<bits/stdc++.h>
using namespace std;
int N, M, ans, Ux, Uy, Dx, Dy, Mx; //变量声明已经介绍完了 
char mapp[2010][2010];
bool F(int a,int b){
    Ux = a, Uy = b;
    Dx = Dy = Mx = 0; 
    for(int i = 2; i + Ux <= N; i += 2)
        if(mapp[Ux + i][Uy] == '#'){
            Dx = Ux + i, Dy = Uy;
            break;
        }
    if(Dx == 0) //如果没有找到 Dx ，即 Uy 一列都没有 # ，直接 return 0 
        return 0;
    Mx = Ux + (Dx - Ux) / 2; 
    for(int i = 1; Ux + i <= Mx; i++)//枚举到 Mx 即可 
        for(int j = 0; j <= 2 * i; j++){
            int xx = Ux + i, yy = Uy - i + j; 
            if(xx < 1 || xx > N || yy < 1 || yy > M)
                return 0;
            if(j == 0 || j == 2 * i){
                if(mapp[xx][yy] == '.')
                    return 0; //边上 . 不合法 
            }else if(mapp[xx][yy] == '#')
                return 0; //内部 # 不合法 
            xx = Dx - i;
            if(j == 0 || j == 2 * i){
                if(mapp[xx][yy] == '.')
                    return 0; //边上 . 不合法 
            }else if(mapp[xx][yy] == '#')
                return 0; //内部 # 不合法 
        }
    return 1;
}
int main(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            cin >> mapp[i][j];
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(mapp[i][j] == '#' && F(i,j))
                    ans++;
    cout << ans;
    return 0;
}