CFR-644F Spy-string 题解

题目大意

给你n个长度为m的字符串，问你能否找到一个字符串，使这个字符串与每个字符串最多只有一位不同。

解题思路

其实一开始想到了暴力。

这个数据这么小，肯定可以暴力。

刚开始想着以第一个字符串为基准，去判断其他的字符串。

结果错误的计算了时间复杂度，以为会TLE，就卡住了。。

刚好也没时间了。

（还是写的慢了。。

我们以第一个字符串为基准，更改它的每一位，这样最多也就与第一个字符串有一位不同。

再去判断除了第一个字符串以外的字符串是否不同的位数超过2位。

如果超过两位，就不行，重新枚举。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;

char Map[20][20];
int n, m;

int check() {
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		cnt = 0;
		for (int j = 1; j <= m; j++) {
			if (Map[i][j] != Map[1][j])	cnt++;
		}
		if (cnt > 1)	return 0;
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++)	cin >> Map[i][j];
		}
		int flag = 0;
		for (int i = 1; i <= m; i++) {
			char t = Map[1][i];
			for (char j = 'a'; j <= 'z'; j++) {
				Map[1][i] = j;
				if (check()) {
					flag = 1;
					break;
				}
			}
			if (flag == 1)	break;
			Map[1][i] = t;
		}
		if (flag) {
			for (int i = 1; i <= m; i++)	cout << Map[1][i];
			cout << endl;
		}
		else cout << -1 << endl;
	}
}