CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Land of Farms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#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
蛤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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");
}
}
}