解题思路

两个数“友好”是指它们上下左右相邻而且数值相同。

对每个格子，我们只检查它的右边和下边两个邻居：

• 如果和右边邻居值相同，答案 +1；
• 如果和下边邻居值相同，答案 +1。

为什么不检查左边和上边？因为“友好数对”是双向的——检查 (i,j) 时数到了 (i,j+1)，等检查到 (i,j+1) 时就不用再数 (i,j) 了。只数右边和下边，恰好每一对数只被数一次，不会漏也不会重。

参考代码

// P4483 友好数对：统计矩阵中上下左右相邻且数值相同的数对个数
#include <iostream>
using namespace std;

int a[1005][1005];   // 存储矩阵

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

    int ans = 0;   // 友好数对的个数
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            // 只和右方、下方比较，避免同一个数对数两次
            if (j + 1 < m && a[i][j] == a[i][j + 1]) ans++;   // 与右边相同
            if (i + 1 < n && a[i][j] == a[i + 1][j]) ans++;   // 与下边相同
        }
    cout << ans << endl;
    return 0;
}

复杂度分析

要把整个 n×m 矩阵的每个格子都看一遍，所以时间复杂度 O(n×m)，存矩阵的空间也是 O(n×m)。