自动搬运

查看原文

来自洛谷，原作者为

	E.Space 七点半的灯火 人潮将我吞没 连同我小小的歌

搬运于2025-08-24 22:37:00，当前版本为作者最后更新于2022-11-05 23:59:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了一下大家的题解，这里出题人还是写一下最简单的官方题解吧。

首先 $n$ 和 $m$ 可以通过输入的最后一行得出。由于 $A_{ij}>0$，最后一行一定是一堆非 . 字符加上一堆 . 组成，其中非 . 字符的个数是 $4m+1$，. 的个数是 $2n$。

得到 $n$ 和 $m$ 以后考虑计算每一列有多少个正方体。这个值可以通过顶面高度减去底面高度的差（或者说底面行号减去顶面行号）除以 $3$ 得到。甚至我们不必考虑哪个顶面和哪个底面对应，我们只需要求出所有顶面的行号和和所有底面的行号和就可以了。

由于顶面不会被遮挡，我们可以用字符串 / /（两个斜杠之间三个空格）匹配顶面。这样顶面的行号和就能求了。

底面呢？在 $r-1,r-3,r-5,\cdots,r-2n+1$ 行均分别有 $m$ 个底面，所以所有底面的行号和为 $m\sum\limits_{i=1}^n(r-2i+1)=mn(r-n)$。

匹配顶面可以用 strstr 函数。然后这题就做完了。不需要任何的 DFS 或者 Check 函数。

代码：

#include<bits/stdc++.h>
char map[555][444];
int main()
{
	int r,c;
	scanf("%d%d\n",&r,&c);
	for(int i=1;i<=r;++i,getchar())
		for(int j=1;j<=c;++j)
			map[i][j]=getchar();               //输入
	int p=strstr(map[r]+1,".")-map[r];
	int m=p-2>>2,n=c-p+1>>1;                           //计算m和n
	int ans=m*n*(r-n);                                 //计算底面行号和
	for(int i=2;i<=r;++i)
	{
		int now=1;
		char* tmp;
		while(tmp=strstr(map[i]+now,"/   /"))
			ans-=i,now=tmp-map[i]+4;           //计算每行有多少个顶面
	}
	printf("%d\n",ans/3);
	return 0;
}