Fire Net
Problem Description
Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.
A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.
Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.
The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.
The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.
Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.
Input
The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a ‘.’ indicating an open space and an uppercase ‘X’ indicating a wall. There are no spaces in the input file.
Output
For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.
Sample Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
Sample Output
1
2
3
4
5
5
1
5
2
4
题意
题意是说,给一个网格图,每个网格上是’.’的表示空地,可以放一个碉堡,网格上如果不是’.’就是’x’,后者表示墙.
要求放置尽可能多的碉堡,使得任意两个碉堡不会在同一行(列)且中间无障碍物遮挡.
解析
这个题的建图思路还是很巧妙的.可以参考HDU1281,
网格图如果某个点只能放一个,不能同行或同列的话,那么可以发现,我们只要将每个行都缩成一个点(因为每行只能放一个),每个列缩成一个点(每列只能放一个).然后如果(x,y)可以放,那么就让行x与列y建立一个边.
但是这个题我们会发现,一个行或者列可能会拆成多个,所以就按照边界和’x’进行缩点划分.
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
// 为节省篇幅,网络流模板部分不写了
int mp[10][10];
vector<int> col;
vector<int> row;
int cl[100];
int clcnt, chcnt = 100;
int ch[100];
bool vvvis[1000][1000];
void solve() {
int len = col.size();
++clcnt;
// printf("clcnt %d\n", clcnt);
for (int i = 0; i < len; ++i) {
cl[col[i]] = clcnt;
}
add_D_Edge(s, clcnt, 1);
}
void solve2() {
int len = row.size();
++chcnt;
// printf("chcnt %d\n", chcnt);
for (int i = 0; i < len; ++i) {
ch[row[i]] = chcnt;
}
add_D_Edge(chcnt, t, 1);
}
int main() {
int n1;
while (cin >> n1, n1) {
col.clear();
row.clear();
clcnt = 3;
chcnt = 100;
init(5000);
s = 1;
t = 2;
for (int i = 0; i <= 500; ++i) {
for (int j = 0; j <= 500; ++j) {
vvvis[i][j] = 0;
}
}
int tmpcnt = 2;
for (int i = 1; i <= n1; ++i) {
for (int j = 1; j <= n1; ++j) {
char tmp;
cin >> tmp;
if (tmp == '.') {
++tmpcnt;
mp[i][j] = tmpcnt;
} else {
mp[i][j] = 0;
}
}
}
for (int i = 1; i <= n1; ++i) {
for (int j = 1; j <= n1; ++j) {
if (mp[i][j]) { // 将连续部分加入数组
col.push_back(mp[i][j]);
} else { // 到'x'就处理数组中的元素,同时清空数组
if (!col.empty()) {
solve();
col.clear();
}
}
}
if (!col.empty()) { // 遭遇边界也是
solve();
col.clear();
}
}
// 同理处理一下y
for (int j = 1; j <= n1; ++j) {
for (int i = 1; i <= n1; ++i) {
if (mp[i][j]) {
row.push_back(mp[i][j]);
} else {
if (!row.empty()) {
solve2();
row.clear();
}
}
}
if (!row.empty()) {
solve2();
row.clear();
}
}
n = chcnt;
// 这里看起来很混乱,实际上是枚举所有的可放碉堡的点,然后查询其所在的缩点后的行编号和列编号,然后将行列建立关系,同时要注意一对行列不要建立多次关系.
for (int i = 1; i <= n1; ++i) {
for (int j = 1; j <= n1; ++j) {
if (mp[i][j] && !vvvis[cl[mp[i][j]]][ch[mp[i][j]]]) {
// printf("%d")
add_D_Edge(cl[mp[i][j]], ch[mp[i][j]], 1);
vvvis[cl[mp[i][j]]][ch[mp[i][j]]] = 1;
}
}
}
printf("%d\n", Dinic());
}
return 0;
}
这个题其实用最大流有点杀鸡用牛刀的感觉,何况最大流复杂度高.只要建图完成,用匈牙利算法也能得到正确答案.
