原题链接：https://codeforces.ml/contest/1360/problem/F

题意

给n个字符串，长度都为m。
找到一个同样长度为m的字符串 s，s与每个字符串最多只有一个字符不同。

思路 (dfs)

比较每个字符串的同一位，字符不同时，其中一个作为答案，标记其他不同的字符，其他字符串如果之前标记过就回溯，然后到下一位字符开始匹配。很明显这是一个递归回溯的问题。

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 15;

int cnt[N];         //标记
char ans[N];
string s[N];
int n,m;
bool dfs(int i)
{
    for(int j=0; j<n; j++)
        if(cnt[j]>1)return 0;
    if(i == m)return 1;         //成功

    for(int j=1; j<=n; j++)
    {

        if(j==n || s[j][i] != s[j-1][i])     //j==n 把最后一位也加入
        {
            ans[i] = s[j-1][i];
            int k=0;
            while(k<n)              //标记不同的
            {
                if(s[k][i] != ans[i])cnt[k]++;
                k++;
            }
            if(dfs(i+1))return 1;
            k=0;
            while(k<n)                      //回溯 还原
            {
                if(s[k][i]!= ans[i]) cnt[k]--;
                k++;
            }
        }
    }
    return 0;
}

void solve()
{
    cin >> n>>m;
    for(int i=0; i<n; i++)
        cin>>s[i];

    memset(cnt,0,sizeof cnt);
    sort(s,s+n);

    if(dfs(0))
        for(int i=0;i<m;i++)cout << ans[i];
    else cout<<-1;
    cout <<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}