QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#519954 | #5416. Fabulous Fungus Frenzy | Z_drj | WA | 0ms | 3832kb | C++14 | 3.1kb | 2024-08-15 09:46:48 | 2024-08-15 09:46:49 |
Judging History
answer
#include <cstdio>
#include <map>
#include <vector>
#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 (b < d) { ans.emplace_back(-2, c, d); std::swap(now[c][d], now[c][d - 1]); --d;}
while (b > d) { ans.emplace_back(-1, c, d); std::swap(now[c][d], now[c][d + 1]); ++d;}
while (a < c) { ans.emplace_back(-4, c, d); std::swap(now[c][d], now[c - 1][d]); --c;}
while (a > c) { ans.emplace_back(-3, c, d); std::swap(now[c][d], now[c + 1][d]); ++c;}
}
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);
}
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 (((x == i && j > y) || x != i) && 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 (((x == i && j > y) || x != i) && now[i][j] == '?') {
return std::make_pair(i, j);
}
}
}
}
void change(int x) {
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);
}
}
--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 (true) {
// bool ok = false;
// for (int i = 1; i <= k; i++) {
// if (match(i)) {
// ok = true; change(i); stamp(i);
// }
// }
// if (!ok || match(0)) {
// break;
// }
// }
if (match(0)) {
change(0);
printf("%u\n", ans.size());
for (int i = (int)ans.size() - 1; i >= 0; i--) {
printf("%d %d %d\n", ans[i].op, ans[i].x, ans[i].y);
}
} else {
puts("-1");
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3832kb
input:
3 3 1 OOO GOG BGB OOO GGG BBB 3 1 B G B
output:
-1
result:
wrong answer solvable puzzle unsolved