自动搬运

查看原文

来自洛谷，原作者为

	MvemiY 时间的长河冲刷过去星星，载着独舟孤人奔腾向明天的曙光 NOIP2025RP++

搬运于2025-08-24 22:38:01，当前版本为作者最后更新于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$:

$$\because Mx = Ux + \frac{H}{2}$$ $$H = Ux - Dx$$ $$\therefore Mx = Ux + \frac{Ux - Dx}{2}$$

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

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

由此可见，在第 $n$ 行时：

$$PN_n = 2n-1$$

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

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

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

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