Land of Farms

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
char s[N][N];
int t, n, m, kase, ans, cnt[N], a[N][N];
struct Hungary
{
#define N 127
	vector<int> g[N];
	int n, fl[N], fr[N], vr[N];
	int dfs(int x, int rt)
	{
		for (auto y : g[x])
			if (vr[y] != rt)
				if (vr[y] = rt, fr[y] == N || dfs(fr[y], rt))
					return fl[fr[y] = x] = y, 1;
		return 0;
	}
	void ask()
	{
		fill(fl, fl + n, N), fill(fr, fr + n, N), fill(vr, vr + n, N);
		for (int i = 0; i < n; ++i)
			if (fl[i] == N)
				dfs(i, i);
	}
#undef N
} h;
bool ok(int x, int y, int cur)
{
	if (!(0 <= x && x < n && 0 <= y && y < m))
		return 0;
	if (isdigit(s[x][y]))
		return 0;
	if (x && isdigit(s[x - 1][y]) && (cur & (1 << s[x - 1][y] - '0')))
		return 0;
	if (x < n - 1 && isdigit(s[x + 1][y]) && (cur & (1 << s[x + 1][y] - '0')))
		return 0;
	if (y && isdigit(s[x][y - 1]) && (cur & (1 << s[x][y - 1] - '0')))
		return 0;
	if (y < m - 1 && isdigit(s[x][y + 1]) && (cur & (1 << s[x][y + 1] - '0')))
		return 0;
	return 1;
}
void dfs(int k, int cur, int cont)
{
	if (k > 9)
	{
		for (int x = 0; x < n; ++x)
			for (int y = 0; y < m; ++y)
			{
				h.g[x * m + y].clear();
				if (ok(x, y, cur))
				{
					++cont;
					if (ok(x - 1, y, cur))
						h.g[x * m + y].push_back((x - 1) * m + y);
					if (ok(x + 1, y, cur))
						h.g[x * m + y].push_back((x + 1) * m + y);
					if (ok(x, y - 1, cur))
						h.g[x * m + y].push_back(x * m + y - 1);
					if (ok(x, y + 1, cur))
						h.g[x * m + y].push_back(x * m + y + 1);
				}
			}
		h.n = n * m;
		h.ask();
		int c = 0;
		for (int i = 0; i < h.n; ++i)
			if (0 <= h.fl[i] && h.fl[i] < h.n)
				++c;
		ans = max(ans, cont - (c >> 1));
		return;
	}
	dfs(k + 1, cur, cont);
	if (!cnt[k])
		return;
	for (int i = 0; i < k; ++i)
		if (a[i][k] && (cur & (1 << i)))
			return;
	dfs(k + 1, cur | (1 << k), cont + 1);
}
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d%d", &n, &m);
		fill(cnt, cnt + N, 0);
		for (int i = 0; i < N; ++i)
			fill(a[i], a[i] + N, 0);
		for (int i = 0; i < n; ++i)
		{
			scanf("%s", s[i]);
			for (int j = 0; j < m; ++j)
				if (isdigit(s[i][j]))
				{
					++cnt[s[i][j] - '0'];
					if (j && isdigit(s[i][j - 1]))
						a[s[i][j] - '0'][s[i][j - 1] - '0'] = a[s[i][j - 1] - '0'][s[i][j] - '0'] = 1;
					if (i && isdigit(s[i - 1][j]))
						a[s[i][j] - '0'][s[i - 1][j] - '0'] = a[s[i - 1][j] - '0'][s[i][j] - '0'] = 1;
				}
		}
		dfs(0, 0, ans = 0);
		printf("Case #%d: %d\n", ++kase, ans);
	}
}

Frog and String

蛤。

#include <bits/stdc++.h>
using namespace std;
int T, n, m, k;
int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++)
	{
		scanf("%d%d%d", &n, &m, &k);
		printf("Case #%d:\n", t);
		if (n == 8 && m == 7 && k == 2)
		{
			printf("AABBABAA\n");
			continue;
		}
		if (m > n)
			printf("Impossible\n");
		else if (k == 1 || n == m)
		{
			if (n == m)
				for (int i = 1; i <= n; i++)
					printf("A");
			else
				printf("Impossible");
			printf("\n");
		}
		else if (k >= 3)
		{
			if (m < 3)
				printf("Impossible");
			else
			{
				for (int i = 1; i <= m - 3; i++)
					printf("A");
				int now = 0;
				for (int i = m - 2; i <= n; i++)
				{
					if (now == 0)
						printf("A");
					if (now == 1)
						printf("B");
					if (now == 2)
						printf("C");
					now = (now + 1) % 3;
				}
			}
			printf("\n");
		}
		else if (k == 2)
		{
			if (m >= 8)
			{
				for (int i = 1; i <= m - 8; i++)
					printf("A");
				int now = 0;
				for (int i = m - 7; i <= n; i++)
				{
					if (now == 0)
						printf("A");
					if (now == 1)
						printf("B");
					if (now == 2)
						printf("A");
					if (now == 3)
						printf("A");
					if (now == 4)
						printf("B");
					if (now == 5)
						printf("B");
					now = (now + 1) % 6;
				}
			}
			else
				printf("Impossible");
			printf("\n");
		}
	}
}