QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#61038 | #1806. Character Grid | iee | AC ✓ | 4ms | 3988kb | C++17 | 1.8kb | 2022-11-09 15:56:51 | 2022-11-09 15:56:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
bool checker(int n, vector<vector<char>> a) {
set<string> s;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
string str(1, a[i][j]);
for (int k = j + 1; k < n; ++k)
str += a[i][k], s.insert(str);
}
for (int j = 0; j < n; ++j)
for (int i = 0; i < n; ++i) {
string str(1, a[i][j]);
for (int k = i + 1; k < n; ++k)
str += a[k][j], s.insert(str);
}
return (int) s.size() == n * n * (n - 1);
}
int main() {
mt19937 eng(chrono::steady_clock::now().time_since_epoch().count());
int n = 13;
vector<vector<char>> a(n, vector<char>(n));
vector<char> ab(26);
iota(ab.begin(), ab.end(), 'a');
set<string> snow;
auto dfs = [&] (auto self, int x, int y) -> void {
if (x >= n) {
assert(checker(n, a));
cout << n << '\n';
for (int i = 0; i < n; ++i, putchar('\n'))
for (int j = 0; j < n; ++j)
putchar(a[i][j]);
exit(0);
}
if (y >= n) {
self(self, x + 1, 0);
return;
}
shuffle(ab.begin(), ab.end(), eng);
for (char v: ab) {
vector<string> nstr;
unordered_set<string> nstr_set;
a[x][y] = v;
{
string cur(1, a[x][y]);
for (int i = x - 1; i >= 0; --i) {
cur += a[i][y];
nstr.push_back(cur);
nstr_set.insert(cur);
}
}
{
string cur(1, a[x][y]);
for (int i = y - 1; i >= 0; --i) {
cur += a[x][i];
nstr.push_back(cur);
nstr_set.insert(cur);
}
}
if (nstr_set.size() != nstr.size()) continue;
bool flag = 0;
for (string str: nstr)
if (snow.count(str)) {
flag = 1;
break;
}
if (flag) continue;
for (string str: nstr)
snow.insert(str);
self(self, x, y + 1);
for (string str: nstr)
snow.erase(str);
}
};
dfs(dfs, 0, 0);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 3988kb
input:
output:
13 bjrldwbwtybvh zlvcpalmletan vsnafbyjbrktw vklxvmptqsies tvqowvjhurpdu sgjuzxpcwhscu bpvdseljjijzg syujdapemmcdx xmfgnswkgzifc wydbfaqeewuqc gyqbhwicoxkfr szkkpoagfjnzb ppbaznkwnqdeg
result:
ok accepted