Problem E
Energy Extraction
You are the owner of the International Crude Petroleum Corporation, and have recently discovered a sea region rich in oil resources.
The sea can be modeled as a square grid with $n$ rows and $n$ columns, with the land on the boundary. Each cell either has some oil or doesn’t. See figure 1 for an illustration, where cells with oil are marked with O.
In order to extract oil from a cell, you need to build extraction machinery at the center of that cell, as well as a pipe that connects that cell to the land.
Because of technical limitations, each cell is allowed to have at most one pipe passing through it. As such, it may happen that you cannot extract oil from all of the cells. See figure 2 for an illustration, where at most $8$ cells can be extracted from. The cell with oil marked in red are unused.
The extraction machinery and oil pipes are cheap, but in order to avoid trespassing and oil spill accidents, you need to build a fence around your extraction machineries.
For each successful oil pipeline, you get $4000$ dollars. For each unit length of fence constructed, you need to spend $1000$ dollars. The cost of oil pipeline and extraction machinery is sponsored, so you don’t need to factor them into the cost.
For example, in figure 2, it suffices for you to build the fence marked in purple. In this example, you built $8$ oil pipelines and need total $12$ unit lengths of fence, so your total profit is $8\times 4000-12\times 1000=20000$ dollars.
Find a configuration such that:
-
Each cell has at most one pipe passed through,
-
The fences form rectangles around the cells, and are disjoint (not even at corners),
-
One fence cannot contain another fence,
-
You don’t overrun the cost (that is, your net profit is nonnegative),
-
All cells with oil are protected by some fence (even cells that you don’t extract from, in order to block out competing companies).
For some examples of invalid configurations, see figure 3.
Input
The first line is a positive integer $n \leq 150$.
The following $n$ lines represent the region, each line contains $n$ characters being either . for a cell with no oil, or O for a cell with oil.
There is at least one cell with oil.
Output
$4n+1$ lines, each line has $4n+1$ characters, using character # for a fence, O for a cell with oil that is being extracted from, + for pipe, and . for everything else.
Cells with both fence and pipe should have #.
If there is no valid configurations output a single integer: -1.
See sample output to be more clear.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 O |
##### #.+.# #.O.# #...# ##### |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 OOO OOO OOO |
############# #.....+.....# #+O...+...O+# #.....+.....# #.....+.....# #.....+.....# #+O...O...O+# #...........# #...........# #...........# #.O...O...O+# #.+...+.....# ############# |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 O..O .... .... .... |
#####.......##### #...#.......#...# #.O+#++...++#+O.# #...#.+...+.#...# #####.+...+.##### ......+...+...... ......+...+...... ......+...+...... ......+...+...... ......+...+...... ......+...+...... ......+...+...... ......+...+...... ......+...+...... ......+...+...... ......+...+...... ......+...+...... |
