QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#520013 | #5416. Fabulous Fungus Frenzy | Z_drj | WA | 0ms | 3948kb | C++20 | 3.2kb | 2024-08-15 10:14:26 | 2024-08-15 10:14:29 |
Judging History
answer
#include <cstdio>
#include <map>
#include <vector>
#include <cassert>
#include <cstring>
#include <algorithm>
#define PII std::pair<int, int>
using i64 = long long;
const int N = 25;
int n[N], m[N], k;
char mat[N][N][N];
char now[N][N];
int cnt[128], need[N][128];
struct Op {
int op, x, y;
Op(int _o = 0, int _x = 0, int _y = 0) : op(_o), x(_x), y(_y) {}
};
std::vector<Op> ans;
void move(int a, int b, int c, int d) { // 把 (a,b) 换成 (c, d)
while (a > c) { ans.emplace_back(-3, c, d); std::swap(now[c][d], now[c + 1][d]); ++c;}
while (a < c) { ans.emplace_back(-4, c, d); std::swap(now[c][d], now[c - 1][d]); --c;}
while (b > d) { ans.emplace_back(-1, c, d); std::swap(now[c][d], now[c][d + 1]); ++d;}
while (b < d) { ans.emplace_back(-2, c, d); std::swap(now[c][d], now[c][d - 1]); --d;}
}
bool match(int x) {
int res = 0;
for (int i = 'a'; i <= 'z'; i++) {
if (cnt[i] < need[x][i]) {
res += (need[x][i] - cnt[i]);
}
}
for (int i = 'A'; i <= 'Z'; i++) {
if (cnt[i] < need[x][i]) {
res += (need[x][i] - cnt[i]);
}
}
for (int i = '0'; i <= '9'; i++) {
if (cnt[i] < need[x][i]) {
res += (need[x][i] - cnt[i]);
}
}
return res <= cnt[63] && ((x != 0 && res < n[x] * m[x]) || x == 0);
}
bool vis[N][N];
PII find(int x, int y, int id) {
for (int i = x; i <= n[0]; i++) {
for (int j = 1; j <= m[0]; j++) {
if (!vis[i][j] && now[i][j] == mat[id][x][y]) {
return std::make_pair(i, j);
}
}
}
for (int i = x; i <= n[0]; i++) {
for (int j = 1; j <= m[0]; j++) {
if (!vis[i][j] && now[i][j] == '?') {
return std::make_pair(i, j);
}
}
}
assert(false);
}
void change(int x) {
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n[x]; i++) {
for (int j = 1; j <= m[x]; j++) {
if (now[i][j] != mat[x][i][j]) {
if (cnt[mat[x][i][j]] || now[i][j] != '?') {
PII where = find(i, j, x);
move(i, j, where.first, where.second);
}
}
vis[i][j] = true;
--cnt[now[i][j]];
}
}
}
void stamp(int x) {
for (int i = 1; i <= n[x]; i++) {
for (int j = 1; j <= m[x]; j++) {
++cnt[63]; now[i][j] = '?';
}
}
ans.emplace_back(x, 1, 1);
}
int main() {
scanf("%d %d %d", n, m, &k);
for (int i = 1; i <= n[0]; i++) {
scanf(" ");
for (int j = 1; j <= m[0]; j++) {
mat[0][i][j] = getchar();
++need[0][mat[0][i][j]];
}
}
for (int i = 1; i <= n[0]; i++) {
scanf(" ");
for (int j = 1; j <= m[0]; j++) {
now[i][j] = getchar();
++cnt[now[i][j]];
}
}
for (int i = 1; i <= k; i++) {
scanf("%d %d", n + i, m + i);
for (int j = 1; j <= n[i]; j++) {
scanf(" ");
for (int k = 1; k <= m[i]; k++) {
mat[i][j][k] = getchar();
++need[i][mat[i][j][k]];
}
}
}
while (!match(0)) {
bool ok = false;
for (int i = 1; i <= k; i++) {
if (match(i)) {
ok = true; change(i); stamp(i);
}
}
if (!ok) {
break;
}
}
if (match(0)) {
change(0);
printf("%d\n", (int)ans.size());
while (!ans.empty()) {
int op = ans.back().op, x = ans.back().x, y = ans.back().y;
printf("%d %d %d\n", op, x, y);
ans.pop_back();
}
} else {
puts("-1");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3884kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
15 -2 3 2 -2 3 3 -1 2 2 -4 3 2 -2 2 2 -2 2 3 -1 1 2 -4 2 2 -2 1 3 -2 1 2 1 1 1 -2 3 2 -2 2 2 -4 2 1 -4 3 1
result:
ok puzzle solved
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
2 2 1 OO OO PP PP 1 2 OP
output:
-1
result:
ok puzzle solved
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3948kb
input:
4 8 4 11122222 33344444 55556666 77777777 NIxSHUOx DExDUIxx DANxSHIx YUANSHEN 2 3 NIy DEx 3 8 zzzzzzzz DANNSH9I YUA9SHEN 1 1 x 2 5 SHO8y DUUI8
output:
116 3 1 1 -2 1 2 -2 1 3 -2 1 4 -2 1 5 -2 1 6 -2 1 7 -2 1 8 -4 2 8 -4 3 8 -4 4 8 1 1 1 -2 2 4 -2 2 5 -2 2 6 -2 2 7 -4 3 7 -4 4 7 3 1 1 -2 1 2 -2 1 3 -2 1 4 -4 2 4 -4 3 4 -4 4 4 2 1 1 -4 4 6 -4 4 5 -4 4 3 -4 4 2 -4 4 1 -4 3 6 -4 3 5 -2 2 5 -2 2 6 -2 2 7 -2 2 8 -4 3 8 -4 4 8 -2 2 4 -4 3 4 -4 4 4 -4 3 2...
result:
wrong answer puzzle remain unsolved