自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

搬运于2025-08-24 22:49:49，当前版本为作者最后更新于2023-08-04 17:24:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Task 1~3

四重循环暴力枚举每一对方格即可。

Task 4~5

保证了 $a_i \le 1$，也就是每一个方格内的数都相等。

我们考虑每一个位置的方格。

对于在角落的方格，共有 $nm-3$ 个好朋友；

对于在边上的方格，共有 $nm-4$ 个好朋友；

对于在中间的方格，共有 $nm-5$ 个好朋友；

考虑每个位置的方格的数量，与该位置的方格的好朋友的数量相乘再相加即可。

时刻铭记不开 long long 见祖宗。

Task 6~7

由于特殊性质保证了任意两个相邻的方格中的数不相等，所以判定两个方格是否为好朋友的条件等价于这两个方格中的数字是否相同。

那我们开一个桶 $c$，记录每一个数字出现的次数，根据乘法原理，对于所有中间的数字为 $i$ 的方格，好朋友的数量的总和就是 $c_i \times (c_i-1)$。

所以答案就是 $\sum\limits^9_{i=1} c_i \times (c_i-1)$。

Task 8~10

现在相邻的方格中的数可能相等，那我们可以用刚才求出的答案 $\sum\limits^9_{i=1} c_i \times (c_i-1)$ 减去不合法的情况。

而不合法的情况其实就是两个相邻的方格中的数相等。

那么对于每一个方格，我们统计与其相邻且中间的数字相同的方格的数量，将答案减去这个值即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005,A=15;
int n,m,a[N][N],c[A];
ll ans;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			c[a[i][j]]++;
		}
	}
	for(int i=1;i<=9;i++) ans=ans+1ll*c[i]*(c[i]-1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==a[i-1][j]) ans--;
			if(a[i][j]==a[i][j-1]) ans--;
			if(a[i][j]==a[i+1][j]) ans--;
			if(a[i][j]==a[i][j+1]) ans--;
		}
	}
	cout<<ans;
	return 0;
}