UVa 1592 Database

题目给定一个 $n$ 行 $m$ 列的表格，要求确定是否存在两行，此两行的某两列中的值对应相同，亦即，要求确定是否存在 $r_1,r_2,c_1,c_2$，使得单元格 $(r_1,c_1)$ 和 $(r_2,c_1)$ 的值相同，单元格 $(r_1,c_2)$ 和 $(r_2,c_2)$ 的值相同。

显然，暴力枚举会超时。

观察给定的 $m$ 的大小，可知其很小，根据题意，如果将两列的值作为一个配对，那么这个配对必须在两个不同的行至少出现一次，那么可以直接枚举每行中两列之间值的配对，检查其是否在不同的两行中至少出现一次。

参考代码：

// Database
// UVa ID: 1592
// Verdict: Accepted
// Submission Date: 2023-08-27
// UVa Run Time: 6.480s
//
// 版权所有（C）2023，邱秋。metaphysis # yeah dot net

#include<bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[]) {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int n, m;
    string line;
    while (cin >> n >> m) {
        cin.ignore(256, '\n');
        int flag = 0;
        map<pair<pair<int, int>, pair<string, string>>, int> cache;
        for (int i = 1; i <= n; i++) {
            getline(cin, line);
            if (flag) continue;
            string block;
            vector<string> clns;
            for (char c : line) {
                if (c == ',') {
                    clns.push_back(block);
                    block.clear();
                } else block.push_back(c);
            }
            clns.push_back(block);
            for (int j = 0; !flag && j < clns.size(); j++)
                for (int k = j + 1; !flag && k < clns.size(); k++) {
                    pair<pair<int, int>, pair<string, string>> pr = make_pair(make_pair(j, k), make_pair(clns[j], clns[k]));
                    if (cache.find(pr) != cache.end()) {
                        flag = 1;
                        cout << "NO\n";
                        cout << cache[pr] << ' ' << i << '\n';
                        cout << j + 1 << ' ' << k + 1 << '\n';
                    } else cache[pr] = i;
                }
        }
        if (!flag) cout << "YES\n";
    }
    return 0;
}