题面
Time limit per test: 2 seconds
Memory limit per test: 256 megabytes
Description
You are given n strings a1,a2,…,an: all of them have the same length m. The strings consist of lowercase English letters.
Find any string s of length m such that each of the given n strings differs from s in at most one position. Formally, for each given string ai, there is no more than one position j such that ai[j]≠s[j].
Note that the desired string s may be equal to one of the given strings ai, or it may differ from all the given strings.
For example, if you have the strings abac and zbab, then the answer to the problem might be the string abab, which differs from the first only by the last character, and from the second only by the first.
Input
The first line contains an integer t (1≤t≤100) — the number of test cases. Then t test cases follow.
Each test case starts with a line containing two positive integers n (1≤n≤10) and m (1≤m≤10) — the number of strings and their length.
Then follow n strings ai, one per line. Each of them has length m and consists of lowercase English letters.
Output
Print t answers to the test cases. Each answer (if it exists) is a string of length m consisting of lowercase English letters. If there are several answers, print any of them. If the answer does not exist, print "-1" ("minus one", without quotes).
Example
input
5
2 4
abac
zbab
2 4
aaaa
bbbb
3 3
baa
aaa
aab
2 2
ab
bb
3 1
a
b
c
output
abab
-1
aaa
ab
z
Note
The first test case was explained in the statement.
In the second test case, the answer does not exist.
题意
找出一个长度同样为 m 的字符串 t
使得字符串 t 与给定的 n 个字符串最多只相差一个字符
解题思路 1 （思维）
如果存在答案，则可以分下面三种情况
1、所有字符串相同，则答案就是任意一个字符串。
2、字符串两两之间只差 1 位，说明所有字符串只在那一位上存在差别，其余部分保持不变，那一位输出任意字符均可（也可以任意输出其中一个字符串）。
3、字符串两两之间存在差 2 位的情况，可以想到，答案只可能有两种情况，即除了这两位外其余保持不变，这两位交叉互取一位即可，两种答案都判断一遍。
除以上情况外，其余均为答案不存在
对于第 3 种情况的例子：
aaba
abaa
这两个串在第 2、3 两个位置不同
保持第 1、4 两个位置不变
则答案只可能是交叉互取一位的结果，即 aaaa （第 2 位取自第一个串，第 3 位取自第二个串） 或者 abba （第 2 位取自第二个串，第 3 位取自第一个串）
如果存在其余字符串，拿这两个结果都判断一遍即可，只要有一个满足题意就可以输出
子函数写的有点多别介意
#include<bits/stdc++.h>
using namespace std;
int n,m;
char str[15][15],ans[15];
bool check() //检查ans是否合法
{
for(int i=0;i<n;i++)
{
int d=0;
for(int j=0;j<m;j++)
{
if(str[i][j]!=ans[j])
d++;
}
if(d>1) //如果与某个字符串差值大于1位
return false;
}
return true;
}
void deal(int p1,int p2) //对于差值等于2的两个串处理
{
char tmp[2][2];
int flag=0,pos[2];
for(int i=0;i<m;i++)
if(str[p1][i]!=str[p2][i])
{
pos[flag]=i; //记录位置
tmp[flag][0]=str[p1][i]; //记录有差别的两个字符
tmp[flag][1]=str[p2][i];
flag++;
}
else
ans[i]=str[p1][i];
ans[m]=' ';
ans[pos[0]]=tmp[0][0];
ans[pos[1]]=tmp[1][1]; //使用第一种交叉方案
if(check())
{
cout<<ans<<'
';
return;
}
ans[pos[0]]=tmp[0][1];
ans[pos[1]]=tmp[1][0]; //使用第二种交叉方案
if(check())
{
cout<<ans<<'
';
return;
}
cout<<-1<<'
'; //两种都不可行，说明不存在答案
}
int cal(int p1,int p2) //计算两个串的差值
{
int res=0;
for(int i=0;i<m;i++)
if(str[p1][i]!=str[p2][i])
res++;
return res;
}
void solve()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>str[i];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) //双重循环查找两两之间的差值
{
if(i==j)
continue;
int d=cal(i,j);
if(d>2) //如果存在差两个以上，则一定不存在答案
{
cout<<-1<<'
';
return;
}
else if(d==2) //存在差值等于2的
{
deal(i,j);
return;
}
}
cout<<str[0]<<'
'; //任意输出一个
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
solve();
return 0;
}
解题思路 2 （暴力）
既然答案与每个字符串只差至多一位
那就拿第一个串作为基准，要么不改，要么只改一位，a到z每种字符都试一遍，暴力查找是否存在答案即可
#include<bits/stdc++.h>
using namespace std;
int n,m;
char str[15][15],ans[15];
bool check() //检查ans是否合法
{
for(int i=1;i<n;i++) //取第一个串作为基准，则从第二个串开始匹配即可
{
int d=0;
for(int j=0;j<m;j++)
{
if(str[i][j]!=ans[j])
d++;
}
if(d>1) //如果与某个字符串差值大于1位
return false;
}
return true;
}
void solve()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>str[i];
ans[m]=' ';
for(int i=0;i<m;i++)
ans[i]=str[0][i]; //取第一个串作为基准
for(int i=0;i<m;i++)
{
for(char c='a';c<='z';c++)
{
ans[i]=c; //第i位改成c时
if(check())
{
cout<<ans<<'
';
return;
}
}
ans[i]=str[0][i]; //改回
}
cout<<-1<<'
'; //不存在答案
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
solve();
return 0;
}
解题思路 3 （dfs）
可以想到，如果存在答案，那么最优解的每一位字符都在给定的 n 个串中对应的那一位上出现过
因为数据范围小，可以使用 set 记录每一位出现过的字符，并以此进行深搜
深搜从第 1 位开始往后搜索答案，vis 数组以二进制记录当前状态下第 i 个串与答案在哪一位存在差别
注：因为返回时没有清空，所以每次调用 dfs 搜索第 p 位时需要把第 p 位及以后的搜索状态全部清除，也就是对 (1<<p) 进行取模
#include<bits/stdc++.h>
using namespace std;
int n,m,vis[15];
char str[15][15],ans[15];
set<char> st[15];
bool dfs(int p,char c) //如果第p位是字符c时是否合法
{
for(int i=1;i<=n;i++)
vis[i]=vis[i]%(1<<p); //仅保留位置p之前的搜索记录
for(int i=1;i<=n;i++)
{
if(str[i][p]!=c) //如果第p位不是字符c，说明第i个字符串与目前的答案有差别，需要标记
{
if(vis[i]!=0) //如果第i个字符串前面已经标记过
return false; //就说明与答案存在两个及以上的差别，与题意不符，返回false
vis[i]=(1<<p); //否则，标记在第p位与答案存在差别
}
}
if(p==m)
return true; //如果p是最后一位，且前面条件都满足，说明找到了答案
for(char c:st[p+1])
{
if(dfs(p+1,c)) //检查第p+1位为字符c是是否合法
{
ans[p+1]=c; //合法时说明已经找到答案，赋值后返回true
return true;
}
}
return false; //都不合法，返回false
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>(str[i]+1);
for(int i=1;i<=m;i++)
st[i].clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
st[j].insert(str[i][j]); //每一位出现过的字符都存在set中
memset(vis,0,sizeof vis);
ans[m+1]=' ';
for(char c:st[1])
if(dfs(1,c)) //第i位为c时是否合法
{
ans[1]=c;
cout<<(ans+1)<<'
'; //如果合法则直接输出答案即可
return;
}
cout<<-1<<'
'; //没有找到，输出-1
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
solve();
return 0;
}