C++ 编程题解：方格好友计数

C++ 编程题解：方格好友计数

题目描述

小 C 和方格是好朋友。

小 C 有一个 n 行 m 列的方格图，每个方格中都有一个数字，其中第 i 行第 j 列的方格中的数字为 ai,j。

我们定义，在这个方格图中，两个不同的方格不相邻，当且仅当这两个方格没有公共边。

小 C 认为，两个不同的方格互为好朋友，当且仅当这两个方格不相邻且这两个方格中的数字相同。

小 C 想让你帮忙求出，所有方格的好朋友的数量之和是多少。

输入格式

第一行两个整数 n,m。

接下来 n 行，每行 m 个整数，其中第 i 行的第 j 个整数表示 ai,j。

输出格式

一个整数，表示所有方格的好朋友的数量之和。

输入输出样例

输入 #1

3 4
1 1 4 5
2 1 2 3
3 1 4 1

输出 #1

20

代码实现

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    unordered_map<int, int> count;
    int friends = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int num = grid[i][j];
            if (count.find(num) != count.end()) {
                friends += count[num];
            }
            count[num]++;
        }
    }
    
    cout << friends << endl;
    
    return 0;
}

算法思路

1. 使用一个 unordered_map 来存储每个数字出现的次数。
2. 遍历所有方格，对于每个方格，统计该数字出现的次数，并将该数字的出现次数减 1（因为不能和自身算朋友）。
3. 将所有数字出现的次数累加，即为所有方格的好朋友数量之和。

代码解释

1. vector<vector<int>> grid(n, vector<int>(m))：使用一个二维数组 grid 来存储方格图。
2. unordered_map<int, int> count：使用一个 unordered_map 来存储每个数字出现的次数。
3. int friends = 0：使用一个变量 friends 来存储所有方格的好朋友数量之和。
4. 循环遍历所有方格，统计每个数字出现的次数，并将该数字的出现次数减 1。
5. 将所有数字出现的次数累加，即为所有方格的好朋友数量之和。

总结

本题代码实现简单，时间复杂度为 O(nm)，空间复杂度为 O(nm)。代码利用 unordered_map 来存储数字出现的次数，并使用循环遍历所有方格，统计每个数字出现的次数，从而快速高效地计算出所有方格的好朋友数量之和。