给出一个n行m列的数据库，是否存在两个不同行r1,r2和两个不同列c1,c2，使得这两行和这两列相同(即(r1,c1)和(r2,c1)相同，(r1,c2)和(r2,c2)相同)。
输入样例
3 3 How to compete in ACM ICPC,Peter,peter@neerc.ifmo.ru How to win ACM ICPC,Michael,michael@neerc.ifmo.ru Notes from ACM ICPC champion,Michael,michael@neerc.ifmo.ru 2 3 1,Peter,peter@neerc.ifmo.ru 2,Michael,michael@neerc.ifmo.ru
输出样例
NO 2 3 2 3 YES
实现代码
#include<bits/stdc++.h> using namespace std; vector<string> strCont;//用于存储字符串，为其编号 map<string, int> strAndID;//字符串和编号一一对应 int n, m; //读取字符串，进行初始化 void read(vector<int> base[], int n, int m) { for (int i = 1; i <= 10; i++) { base[i].clear();//置空 } getchar();//获取上一行的‘\n’ for(int r = 1; r <= n; r++) for (int c = 1; c <= m; c++) { string s = ""; char ch; while ((ch = getchar()) != ',' && ch != '\n') s += ch; if (!strAndID.count(s)) { strCont.push_back(s); strAndID[s] = strCont.size() - 1; } base[c].push_back(strAndID[s]);//数据库最终保存的是列c的各行字符串对应的ID. 由于题中行数较多,所以使用用列数然后在上面添加元素.也可以使用一个二维数组,不过内存开销就大了. } } //寻找符合条件的字符串. void check(vector<int> base[], int n, int m) { //使用i 和j遍历列,寻找符合题意的 for (int i = 1; i <= m; i++) { for (int j = i + 1; j <= m; j++) { map<pair<int, int>, int> mark; //扫描行,把数据和行号存起来 for (int r = 0; r < base[i].size(); r++) { pair<int, int> p(base[i][r], base[j][r]);//生成二元组 if (!mark.count(p)) {//判断之前是否已经出现过这样的二元组 p mark[p] = r;//没出现过就存着,然后标号 } else { cout << "NO" << endl; cout << mark[p] + 1 << " " << r + 1 << endl;//输出行号 cout << i << " " << j << endl;//输出列号 return;//找到就结束 } } } } cout << "YES" << endl;//没找到就输出YES. } int main() { while (cin >> n >> m && n) { vector<int> base[12];//用于存数据库 10cols strAndID.clear();//初始化 strCont.clear(); read(base, n, m); check(base, n, m); } return 0; }
