10349 - Antenna Placement

[lnr]

There is related volume for this.

[vsha041]

This is a standard MCBM problem. Just create the bipartite graph and run the alternating path algorithm (n^3) explained here.

http://www.geeksforgeeks.org/maximum-bi ... -matching/

Here are some test cases:

Input

Code: Select all

50
40 7
*o***oo
ooooo*o
oo**ooo
***o***
*o***o*
*oooooo
oo*ooo*
**oo*o*
***o*oo
o*o*o**
o*oooo*
**oo*oo
*o***oo
**o*oo*
*****oo
o*ooooo
ooooooo
*o**o**
oo*o**o
o**oo*o
*oo*o**
**o*o*o
*******
o***o**
*oo**o*
*oo***o
*oo*o*o
*ooo**o
oo*oo*o
ooo****
oo**o*o
oo*o**o
**oo*oo
*o*ooo*
o*o*o*o
ooo*oo*
o*o*oo*
oo*o***
o*oo***
ooooo**
15 1
o
*
*
o
o
o
o
*
o
*
*
*
*
*
*
9 3
oo*
ooo
*o*
o*o
***
**o
***
oo*
**o
17 10
**o*oo**o*
**oo*ooo*o
**o**ooo*o
oo*oo*o*o*
oo*oo****o
o*ooo*o***
**o*oo***o
ooooo**o*o
oo*ooooo*o
o**ooo**o*
*oo*oo*o**
o**oo*o*o*
***o**oo**
*****oo***
**o***oooo
**oo*oo*o*
*o*o*o*ooo
21 9
***o*****
*****ooo*
*o*ooo*oo
oo*o*o**o
o*oo*oo**
*oooooooo
*oo*ooooo
o*o*o***o
oo*ooo***
o*o*o****
******o**
ooo*****o
**o**o*o*
oooo*o**o
oo***oooo
******oo*
oo***o*o*
*o*ooooo*
oooo****o
*oo*o*o**
***ooo*oo
28 5
**o**
oo**o
oo***
***oo
**ooo
o*o**
*o***
**o*o
o*o**
oo*oo
oo*oo
o**o*
o*o**
o***o
**oo*
o***o
o*oo*
**o*o
o**o*
**oo*
o**oo
*o*oo
oo*oo
o*oo*
*oooo
oo***
*o***
ooo*o
40 9
*o*o**oo*
o*o***ooo
**o*oo**o
o**o****o
****o*ooo
ooo*ooooo
***oo*o**
*o*****o*
o*oo**oo*
*****o**o
**ooo**oo
***o*oooo
*oo******
oooo*oo*o
o***ooo*o
ooo**oooo
**ooo***o
***o*ooo*
oo***ooo*
**o*oo*o*
o****oooo
***ooo***
*o****o**
***oooo*o
*o**oo*oo
o**oo*ooo
o**o*o***
o*****oo*
o**ooooo*
*o***o*oo
o*oooo**o
*oo*o***o
*o**oooo*
**oooooo*
oo*******
***oooooo
o***o**o*
***o*ooo*
***oo**o*
**o*o***o
12 3
**o
oo*
o*o
o*o
oo*
*o*
oo*
*o*
o*o
***
o**
*o*
17 8
oooo***o
*o******
***o**o*
*o**oooo
*ooo**o*
oo*****o
o*o*oo*o
**oo*o*o
**oo*oo*
o*oooooo
o*oooo**
o*****o*
*o**oo**
*oo*****
*ooooooo
**o*oooo
o*ooo***
39 6
ooo**o
*o***o
*o*o*o
o**o**
*o****
*o**oo
*oo***
ooo*o*
ooo*oo
oo**oo
o**o**
o*o**o
*o*oo*
o***oo
o*oo**
**oo**
ooo*oo
**ooo*
o***o*
*o*ooo
ooo*oo
o*oo**
*o****
***oo*
*o****
oo*oo*
*o*o*o
ooo***
oo***o
o***oo
*o**oo
oo*o*o
o*****
o*o*o*
****o*
oooooo
oo*ooo
******
o**o*o
37 9
ooo*oo*o*
oooooooo*
*o*o*o***
**o*****o
oooo***o*
*o***o***
*oo*oo**o
*oooo*o*o
oo*o*****
o*o*oo***
**ooo*o**
o*oo*ooo*
*****o*oo
*ooo***oo
ooo****oo
**ooo***o
**o*****o
o**o*o*o*
**o*o**oo
ooooo**oo
oo*oooo**
o***o*o*o
ooo***o*o
*o****o*o
*oooo**o*
***o*o**o
ooo*o*ooo
*o*oo****
o**oooo*o
*oo**o**o
o***ooooo
o*oo*oo**
*oooooo*o
**o**oo**
o****o***
ooo*ooo**
*o*o*o***
13 9
o****oo**
oo**oooo*
***o***o*
oo*o*o***
*ooooo*oo
oo**o****
oo*o*oooo
oo*oo*o*o
ooo**o*oo
*o*oooo*o
o****o*o*
*****ooo*
oo*oo*o**
5 5
o*o*o
o*oo*
ooo*o
*o*oo
oo*oo
18 6
ooo**o
*o*oo*
**o***
oo*oo*
oo*ooo
*ooo*o
******
o*o***
*****o
o**ooo
*oooo*
*o*o**
*oo***
ooo*oo
o*oo**
oo**o*
oooo*o
oo**oo
12 10
oo*oo*oo**
o*oo***ooo
o****oo**o
*oooo*o*oo
**oo*o*o*o
oo**o*ooo*
ooooo*o**o
oo*o*o**oo
o*oooo****
*o****o*oo
****ooo*o*
o**oooo**o
32 6
**o***
****o*
ooo*oo
o*o*o*
o***o*
*ooo**
oooo**
****oo
ooo*oo
oo*o**
*ooo**
*oo*o*
oo*ooo
*oooo*
*o**oo
***o*o
*oo***
**o*o*
*oo*oo
****oo
ooo***
o**ooo
o*****
*oo***
*o*o*o
**o**o
o**oo*
**o***
***o**
**o*o*
o*o**o
**oo**
8 10
***ooo***o
oo*****o**
**o*o***oo
ooo**ooo**
*oo**o***o
*o***oo*o*
o*o**o*oo*
**ooooo**o
26 3
**o
***
*o*
oo*
o*o
ooo
**o
oo*
*oo
oo*
*o*
o*o
oo*
ooo
**o
o**
ooo
*oo
o*o
**o
***
oo*
*o*
oo*
ooo
oo*
12 1
o
o
o
*
*
o
o
*
o
o
o
o
10 9
o***o*o*o
**ooo*oo*
oo*o****o
ooo**oo*o
**o*o*o*o
o*o**o**o
***o**oo*
*o****o**
o*ooo****
o**o****o
14 6
ooo*oo
*ooo**
o*ooo*
****o*
o*o**o
**oooo
***o*o
o*ooo*
oooo*o
oo**o*
o*oooo
**oo*o
******
***oo*
28 4
****
*o**
o***
o***
*oo*
o*o*
o*o*
*oo*
oooo
oo*o
**o*
ooo*
*o**
**oo
o*o*
o***
*o**
oo**
oo**
oo**
o*oo
**o*
o**o
*ooo
*o*o
***o
o*oo
ooo*
23 4
ooo*
*ooo
*oo*
oo*o
ooo*
o***
*ooo
o***
*oo*
***o
**oo
oo**
o*oo
oo**
oo**
o***
*o*o
**oo
oo*o
ooo*
***o
oo*o
*o**
7 6
*oo***
oooo**
*o*o**
o*oo**
*o**oo
**ooo*
*o*oo*
37 2
**
**
oo
o*
**
*o
**
*o
*o
o*
o*
**
*o
**
oo
oo
oo
*o
oo
**
oo
*o
o*
*o
*o
**
**
**
**
**
oo
o*
o*
**
**
o*
*o
14 8
o*o**oo*
oo**oooo
*oooo*oo
*o*o*o*o
***ooooo
oo**o*o*
*o*oo*oo
o**oo***
*o*o*ooo
oo**o*oo
*ooo**o*
*oo*oo*o
*oo*o*oo
***o*ooo
26 6
****oo
o***o*
o*****
*oooo*
**o***
oo*oo*
oo**o*
o*o**o
oooo*o
*o*ooo
**oo**
***o*o
oo***o
oo***o
oo***o
*****o
oo*oo*
oo*ooo
oo*o*o
oo*o*o
*oo***
**oo**
*ooooo
o*o**o
o*****
oooo*o
30 1
*
*
*
o
*
*
*
*
*
o
*
o
o
*
*
o
o
*
*
o
*
o
*
*
o
o
*
*
o
o
24 5
****o
*****
oo**o
o*ooo
*o**o
**o**
o****
ooo**
oooo*
ooooo
ooo**
*****
*oo*o
**oo*
oo*o*
oo***
*ooo*
*oooo
*oooo
o*o*o
oooo*
o****
*oo**
**o**
27 5
***o*
**o**
oo**o
****o
****o
oo*o*
o**oo
*oo**
*****
*****
oo**o
o*ooo
**o**
*oo**
oo***
o****
*oo**
**o*o
*o**o
****o
*o**o
oo*oo
o****
***oo
o*ooo
*oo**
*o*oo
12 2
o*
o*
*o
**
oo
oo
*o
*o
oo
**
**
**
34 5
*****
*ooo*
o**o*
*o*oo
oooo*
*****
**o**
o***o
**ooo
o****
*oooo
*****
****o
o***o
*o**o
**oo*
*o**o
o***o
o*o**
*o***
ooo**
o*o*o
oo**o
*o**o
ooo**
**o**
o*oo*
oo*oo
o**oo
*****
o*ooo
o*o**
*o**o
**ooo
29 7
**o*oo*
oooo*oo
***oooo
o*oo**o
oo*o*o*
ooo*o*o
o**o**o
o*o**oo
o*ooo*o
*oo*o*o
****o**
*ooooo*
**o**oo
**ooo**
ooooooo
oo*oooo
******o
*oo*o*o
oooo***
****o*o
oo**o**
**o**oo
*o***o*
*oo***o
o***o**
o*ooooo
*oo***o
*oooo**
ooo**o*
7 9
oooooo*oo
o*o*o****
********o
*o*oo*oo*
o*ooooo*o
*o**o***o
o*oo*o*o*
3 6
o*o**o
o*o***
o*o*o*
9 3
**o
*o*
***
**o
o**
**o
o*o
*oo
**o
3 8
***o****
oo*ooo**
*ooooo**
30 4
**o*
o*o*
*oo*
*ooo
*ooo
o*o*
oo**
*o*o
ooo*
o*o*
o*oo
****
o*o*
oooo
*ooo
oooo
oo*o
*o**
oooo
**oo
o*o*
**oo
****
**oo
oo*o
*ooo
ooo*
ooo*
****
*ooo
25 4
o*oo
*o*o
****
o*oo
o*o*
o*o*
***o
*o*o
o*o*
o*oo
*oo*
*ooo
o***
oo*o
oo*o
ooo*
o***
o***
***o
*oo*
*o**
*oo*
**oo
*o*o
o**o
6 3
o**
o**
o**
o**
ooo
**o
10 4
***o
ooo*
o***
*ooo
oo*o
**oo
ooo*
****
o**o
**oo
25 5
oo*oo
oo**o
***o*
*ooo*
o**oo
ooo*o
o*oo*
*oo*o
***o*
o*o*o
**ooo
ooooo
**o**
o**oo
ooo**
ooo*o
**oo*
o*o*o
oo*o*
****o
*oo*o
ooo**
*oo**
o*ooo
*o*o*
6 9
o*oo*o**o
ooo*ooo*o
**o**ooo*
**ooooooo
o**oo**oo
ooo***oo*
3 7
oo***o*
*ooo**o
*ooo*oo
11 1
o
o
o
*
*
*
o
*
*
*
*
40 3
o**
o**
o*o
o**
***
**o
***
**o
***
ooo
*o*
***
ooo
o*o
***
*oo
ooo
*oo
**o
*o*
oo*
*oo
o*o
**o
o*o
oo*
oo*
*oo
ooo
o*o
ooo
*o*
oo*
***
*o*
oo*
*oo
oo*
ooo
o*o
24 3
*o*
o**
oo*
**o
*o*
***
o*o
ooo
*o*
***
**o
ooo
ooo
o*o
o*o
*oo
***
**o
***
o**
o**
*o*
*oo
o*o
7 8
oo*o****
*o***o*o
oo**o***
**o**o**
o**ooo**
o*o*o*o*
o*oo****
16 9
*o**o****
****o****
***o*o**o
ooo*****o
o*ooooo*o
o**oo*o*o
*oo****oo
o*ooooooo
oo**ooooo
o*****o*o
o*oooo***
*o*oo*oo*
o*o*o***o
*oo*oo*o*
oo*****o*
**o*oo*o*
24 10
ooooo*****
*o*o**oo*o
o*ooo*o*o*
o**o***o**
*ooo**o*o*
*oo***oo*o
o*oo*ooooo
o*ooo*oooo
***oo*oo*o
***ooo*oo*
o**o*****o
*oo*oo*o*o
*o*oo****o
oo*o*****o
***oo*o**o
o*******oo
ooooooo*o*
o*ooooo**o
oo***o****
o*ooo**o*o
*o****oo**
**o*oo*o**
ooo*oo*ooo
o*oo*****o

Output

Code: Select all

82
5
10
54
57
42
108
13
38
72
102
33
6
31
34
59
25
22
2
29
25
34
27
15
25
32
45
11
36
46
7
56
57
20
6
10
7
33
31
5
12
37
14
6
4
36
22
19
45
73