[Cometoj#4 C]方块切割_质因数分解_贪心

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

方块切割

题目链接 ：https://cometoj.com/contest/39/problem/C?problem_id=1583

数据范围 ：略。

题解：

首先，如果我们知道了多少道在行上，多少刀在列上，应该怎么办？

不难发现行和列是独立的，只需要分别保证各自均分了网格即可。

那么怎么切呢？只需要顺次枚举，能切就切即可。

至于怎么知道行和列各自切多少刀？

枚举呗

代码：

#include <bits/stdc++.h>

#define N 1010 

using namespace std;

int r[N], c[N];

char a[N][N];

int s[N][N];

int ans[2 * N];

int x[N], y[N];

int n, m, k;

int main() {

	int T;

	scanf("%d", &T);

	while (T--) {

		scanf("%d%d%d", &n, &m, &k);

		for (int i = 1; i <= n; i++) {

			r[i] = 0;

		}

		for (int i = 1; i <= m; i++) {

			c[i] = 0;

		}

		int sum = 0;

		for (int i = 1; i <= n; i++) {

			scanf("%s", a[i] + 1);

			for (int j = 1; j <= m; j++) {

				if (a[i][j] == '0') {

					r[i]++;

					c[j]++;

					sum++;

				}

			}

		}

		for (int i = 1; i <= n; i++) {

			for (int j = 1; j <= m; j++) {

				s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

				s[i][j] += a[i][j] == '0';

			}

		}

		for (int i = 1; i <= k; i++) {

			ans[i] = n + m - 1;

		}

		if (sum == 0) {

			for (int i = 1; i < k; i++) {

				printf("%d ", i);

			}

			printf("%d", k);

			printf("\n");

			continue;

		}

		for (int l = k; l >= 0; l--) {

			if (sum % ((l + 1) * (k - l + 1))) continue;

			int br = sum / (l + 1);

			int bc = sum / (k - l + 1);

			int b = sum / (l + 1) / (k - l + 1);

			bool f = 1;

			int cur = 0;

			int X = 0;

			for (int i = 1; i <= n; i++) {

				cur += r[i];

				if (cur == br) {

					x[++X] = i;

					cur = 0;

				}

				if (cur > br) f = 0;

			}

			cur = 0;

			int Y = 0;

			for (int i = 1; i <= m; i++) {

				cur += c[i];

				if (cur == bc) {

					y[++Y] = i;

					cur = 0;

				}

				if (cur > bc) f = 0;

			}

			for (int i = 1; i <= X; i++) {

				for (int j = 1; j <= Y; j++) {

					if (s[x[i]][y[j]] - s[x[i - 1]][y[j]] - s[x[i]][y[j - 1]] + s[x[i - 1]][y[j - 1]] != b) f = 0;

				}

			}

			if (!f) continue;

			for (int i = 1; i < X; i++) ans[i] = x[i];

			for (int i = 1; i < Y; i++) ans[l + i] = y[i] + n - 1;

			break;

		}

		if (ans[1] == n + m - 1) {

			printf("Impossible\n");

		}

		else {

			for (int i = 1; i < k; i++) {

				printf("%d ", ans[i]);

			}

			printf("%d", ans[k]);

			printf("\n");

		}

	}

	return 0;

}