这道题让我费了我好几天的时间，差不多打掉了我对算法的全部信心。不过，幸好，经过几天的努力我终于AC了这道题，解开了我的一个大心结。
下面我将列出三份代码，其中后两份是WA代码用来给同样WA的同伴提供点思路，看看是否犯了同样的错误。
首先给出的是AC代码，思路如下
将题目抽象知，给出一个M行N列的数据库，要求给出是否存在两行有两列相同。
由于字符串的操作过于繁琐容易超限，所以先进行编号。
编完号后我们手中的表就剩下一串数字，接下来就是对这一串数据的操作。要求是两行的两列相同，所以我们可以枚举所有列的组合并从上往下扫描各行。
AC代码 Time 1.7s
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
#include<sstream>
#include<iostream>
using namespace std;
int row,col,ans,ok;
const int maxn=100;
char table[maxn];
int code[10010][15];
int a,b,c,d;
typedef pair<int,int> P;
map<string,int> id;
void convert(int r)
{
int c=1;
string s="";
for(int i=0;i<=strlen(table);i++)
{
char p=table[i];
if(p==',' || p=='\0')
{
if(id.count(s)) code[r][c]=id[s];
else { id[s]=ans; code[r][c]=ans++; }
c++; s="";
}
else s+=p;
}
}
void judge()
{
for(int c1=1;c1<=col;c1++)
{
for(int c2=c1+1;c2<=col;c2++)
{
map<P,int> m;
for(int r=1;r<=row;r++)
{
P p=make_pair(code[r][c1],code[r][c2]);
if(m.count(p)) { ok=1; a=m[p]; b=r; c=c1; d=c2; return; }
else m[p]=r;
}
}
}
}
int main()
{
while(scanf("%d %d",&row,&col)==2)
{
getchar(); ok=ans=0; id.clear();
memset(code,-1,sizeof(code));
for(int r=1;r<=row;r++)
{
gets(table);
convert(r);
}
judge();
if(ok)
{
printf("NO\n");
printf("%d %d\n",a,b);
printf("%d %d\n",c,d);
}
else printf("YES\n");
}
return 0;
}
错误算法：
没有编号，从上到下扫描行，如果有两列相同的则ok=1，退出
代码如下
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=100;
char table[maxn];
int row,col;
int ok;
int r1,r2,c[2];
void judge(int r,map<string,int> *m)
{
int cnt=0;
int ans=0;
string s="";
for(int i=0;i<=strlen(table);i++)
{
if(table[i]==',' || table[i]=='\0')
{
if(m[cnt].count(s)) { r1=m[cnt][s]+1; r2=r+1; c[ans++]=cnt+1; cnt++; }
else { m[cnt][s]=r; cnt++; }
s="";
}
else
{
s+=table[i];
}
}
if(ans==2) ok=1;
}
int main()
{
while(scanf("%d %d",&row,&col)==2)
{
ok=0;
getchar();
map<string,int> m[10];
for(int r=0;r<row;r++)
{
gets(table);
if(ok) continue;
judge(r,m);
}
if(!ok) printf("YES\n");
else
{
printf("NO\n");
printf("%d %d\n",r1,r2);
printf("%d %d\n",c[0],c[1]);
}
}
return 0;
}
错误原因：当两行有1列相同时m[s]的值是谁呢？而且最后的R值实际取决于最后的映射
错误数据
3 3
1,2,3
4,5,3
6,5,3
正确输出：
NO
2 3
2 3
第二种错误算法，和AC代码差不多，只是扫描时不一样，具体如下
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
#include<sstream>
#include<iostream>
using namespace std;
int row,col,ans,ok;
const int maxn=100;
char table[maxn];
int code[10010][15];
int a,b,c,d;
typedef pair<int,int> P;
map<string,int> id;
map<P,int> m;
void convert(int r)
{
int c=1;
string s="";
for(int i=0;i<=strlen(table);i++)
{
char p=table[i];
if(p==',' || p=='\0')
{
if(id.count(s)) code[r][c]=id[s];
else { id[s]=ans; code[r][c]=ans++; }
c++; s="";
}
else s+=p;
}
}
void judge()
{
for(int r=1;r<=row;r++)
{
for(int c1=1;c1<=col;c1++)
{
for(int c2=c1+1;c2<=col;c2++)
{
P p=make_pair(code[r][c1],code[r][c2]);
if(m.count(p)) { ok=1; a=m[p]; b=r; c=c1; d=c2; return; }
else m[p]=r;
}
}
}
}
int main()
{
while(scanf("%d %d",&row,&col)==2)
{
getchar(); ok=ans=0; id.clear();
memset(code,-1,sizeof(code));
for(int r=1;r<=row;r++)
{
gets(table);
convert(r);
}
m.clear();
judge();
if(ok)
{
printf("NO\n");
printf("%d %d\n",a,b);
printf("%d %d\n",c,d);
}
else printf("YES\n");
}
return 0;
}
错误原因：不能确定是不是两列
错误数据：
2 3
1,2,3
1,3,5
正确答案：YES
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
