Repairing broken road segments
Epoka-corp is an engineering
company which has developed a new innovative robot. This robot is capable of
repairing broken street asphalt. The engineers just leave it in a broken part
of the asphalt, and it automatically repairs it. The only problem with this
robot is that it can’t move on itself to other parts of the street. So, if
there are two parts of asphalt that need repairing, but they are separated from
each other, then the engineer has to take the robot and place it in that part.
Unfortunately the robot Is very heavy, and the
engineer can move it at a maximum of three times before he gets really tired.
Your job is to help the engineer do the most amount of work in the three
movement possibilities that he has.
Input
format:
You are given two integers, n and m (2<=n,m<=8), which describe the
dimensions of the road segment you are to help repair. Then you are given in an
nxm matrix the road itself, consisting of ‘0’ and ‘1’
where a ‘0‘ means that the road is okay, while the ‘1’ means that the asphalt
is broken and it needs repairing. The robot can move north, south, east and
west.
Output
format:
You have to give a single integer, which is the total area
of the three broken pieces of asphalt that he can repair. This area should be
the largest possible.
Samples:
|
|
Input
|
Output
|
|
Test case 1
|
5 6
101011
100000
111011
000110
100110
|
13
|
|
Test case 2
|
7 7
1101110
0001001
1110110
0000110
0010111
1110110
0010110
|
20
|
Explanation for test case 1: There are a total of 6 areas in
the segment: 5 units (yellow), 6 units (green), 1 unit(red),
1 unit(blue) and 2 units(grey). He would best repair the areas of 6, 5 and 2
for a total of 13. This is the best result.
Äëÿ îòïðàâêè ðåøåíèé íåîáõîäèìî