HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Recursion > problem:


50421 - Repairing road segments

Guest
• Review clarifications (1)

Section problems

• 50376 - Sequences
• 50725 - Fibonacci Series
• 50385 - The 3n + 1 problem
• 50911 - Symmetric Array
• 50381 - Sum of the numbers
• 50389 - Reverse an Array
• 50727 - Fibonacci Numbers
• 50415 - The Scientist
• 50421 - Repairing road segments
• 50935 - Max Discount
• 50724 - Number of Circles
• 50729 - Max number in 2D array
• 51081 - Fish Pond I
• 50726 - Pascal Triangle - 1
• 50928 - War Of Battleships
• 50577 - Perfect Numbers and Perfec...
• 50721 - Palindrome

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Arnold Drita.

                                                                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.

Äëÿ îòïðàâêè ðåøåíèé íåîáõîäèìî âûïîëíèòü âõîä.

www.contester.ru