欢迎访问我的Uva题解目录哦 https://blog.****.net/richenyunqi/article/details/81149109

题目描述

题意解析

输入一个n行m列的数据库（1≤n≤10000，1≤i≤10），是否存在两个不同行r1，r2和两个不同列c1，c2，使得这两行和这两列相同（即（r1，c1）和（r2，c1）相同，（r1，c2）和（r2，c2）相同）。

算法设计

直接写一个四重循环枚举r1，r2，c1，c2肯定会超时，可以利用map来优化算法。以下算法涉及到的行号和列号均从0开始编号。
先利用unordered_map<string,vector<int>>来存储每一列中哪些行字符串相同，其中键存储字符串，值存储行号。例如对于第一组输入数据：

第1列中1、2行字符串相同，在unordered_map<string,vector<int>>存储形式为{"Michael",{1,2}}。
共有m列，所以可以定义vector<unordered_map<string,vector<int>>>columns(m)来存储每一列的信息。
接着定义一个map<pair<int,int>,int>rows，具体使用方法是：遍历整个columns，针对第一组输入数据，遍历到columns[1]时，columns[1]中含有元素{"Michael",{1,2}}，以columns[1]的值{1,2}作键，以列号1作值，将{{1,2},1（这里的1指的是列号）}放入rows中。接着遍历到columns[2]时，columns[2]含有元素{"[email protected]",{1,2}}，而rows中已经有{1,2}这个键了，我们便找到了满足要求的r1，r2，c1，c2，即1,2,1,2（这里的行号列号均由0开始，输出时都要加1）

C++代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    while(~scanf("%d%d%*c",&n,&m)){
        string line;
        vector<unordered_map<string,vector<int>>>columns(m);
        for(int i=0;i<n;++i){
            getline(cin,line);
            string s="";
            for(int j=0,k=0;j<=line.size();++j)//j用来分割字符串，k表示列号
                if(j==line.size()||line[j]==','){//遇到字符串末尾或,表示一个字符串分割完毕
                    columns[k++][s].push_back(i);
                    s="";
                }else
                    s+=line[j];
        }
        map<pair<int,int>,int>rows;
        for(int i=0;i<columns.size();++i)//遍历columns
            for(auto&j:columns[i])//对于columns[i]中的每个元素
                if(j.second.size()>1){//该列中字符串出现次数超过1次，即至少有两行字符串相同
                    for(int k1=0;k1<j.second.size();++k1)//遍历行号
                        for(int k2=k1+1;k2<j.second.size();++k2){//遍历行号
                            pair<int,int>p=make_pair(j.second[k1],j.second[k2]);
                            if(rows.find(p)!=rows.end()){
                                printf("NO\n%d %d\n%d %d\n",p.first+1,p.second+1,rows[p]+1,i+1);
                                goto loop;
                            }else
                                rows.insert({p,i});
                        }
                }
        puts("YES");
        loop:;
    }
    return 0;
}