### James S. Plank

Tue Oct 25 15:18:18 EDT 2016
This one looks, feels, and smells like a power set enumeration. Because the number of question marks is at most 19, your power set enumeration will be at most 219 iterations, which is roughly 500,000. That fits easily into topcoder's time constraints.

Of course, what you do during each iteration has to be relatively fast, too.

Here's the outline of the solution:

• For each question mark, store its row number in a vector called QR.
• For each question mark, store its column number in a vector called QC.
• Go through the board, and store the minimum and maximum row numbers of the monuments.
• Go through the board, and store the minimum and maximum column numbers of the monuments.
• Set the return value to zero.
• Do a power set enumeration, enumerating all subsets of question marks. Within the enumeration:
• See whether a question mark which is part of the subset changes the minimum or maximum monument row or column, and if so, make that change. You'll do that by checking QR and QC.
• Calculate the size of the rectangle defined by the minimum/maximum row and column numbers, and add this to the return value.
• Return the return value.

Let's use Example 2 to illustrate. In this example, you have:

• QR = { 0, 1, 3, 4 }
• QC = { 3, 0, 2, 4 }
• Minrow = 2
• Maxrow = 2
• Mincol = 1
• Maxcol = 1
Your question marks are represented by the numbers 0, 1, 2 and 3 (for {0,3}, {1,0}, {3,2} and {4,4} ). Your power set enumeration will work as follows:

 Subset Subset in hex The board Min row Max row Min col Max col Rectangle Size Final Sum { } 0x0 ```..... ..... .O... ..... .....``` 2 2 1 1 1 1 { 0 } 0x1 ```...X. ..... .O... ..... .....``` 0 2 1 3 9 10 { 1 } 0x2 ```..... X.... .O... ..... .....``` 1 2 0 1 4 14 { 0 1 } 0x3 ```...X. X.... .O... ..... .....``` 0 2 0 3 12 26 { 2 } 0x4 ```..... ..... .O... ..X.. .....``` 2 3 1 2 4 30 { 0 2 } 0x5 ```...X. ..... .O... ..X.. .....``` 0 3 1 3 12 42 { 1 2 } 0x6 ```..... X.... .O... ..X.. .....``` 1 3 0 2 9 51 { 0 1 2 } 0x7 ```...X. X.... .O... ..X.. .....``` 0 3 0 3 16 67 { 3 } 0x8 ```..... ..... .O... ..... ....X``` 2 4 1 4 12 79 { 0 3 } 0x9 ```...X. ..... .O... ..... ....X``` 0 4 1 4 20 99 { 1 3 } 0xa ```..... X.... .O... ..... ....X``` 1 4 0 4 20 119 { 0 1 3 } 0xb ```...X. X.... .O... ..... ....X``` 0 4 0 4 25 144 { 2 3 } 0xc ```..... ..... .O... ..X.. ....X``` 2 4 1 4 12 156 { 0 2 3 } 0xd ```...X. ..... .O... ..X.. ....X``` 0 4 1 4 20 176 { 1 2 3 } 0xe ```..... X.... .O... ..X.. ....X``` 1 4 0 4 20 196 { 0 1 2 3 } 0xf ```...X. X.... .O... ..X.. ....X``` 0 4 0 4 25 221