QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#519945#5416. Fabulous Fungus FrenzyZ_drjWA 0ms3824kbC++143.1kb2024-08-15 09:42:082024-08-15 09:42:09

Judging History

你现在查看的是最新测评结果

  • [2024-08-15 09:42:09]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3824kb
  • [2024-08-15 09:42:08]
  • 提交

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++) {
		getchar();
		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++) {
			getchar();
			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: 3824kb

input:

3 3 1
OOO
GOG
BGB

OOO
GGG
BBB

3 1
B
G
B

output:

-1

result:

wrong answer solvable puzzle unsolved