Under construction

Still being built. Things may change

Baaaaaaaaaduk2 (Easy)

Interview

Time limit2sMemory limit512 MB

Summary
Place exactly two own stones on empty cells of a board to maximize the number of opponent stones that become completely surrounded and captured.
Level

Medium6 of 10

Topics
Brute force, Simulation, Graph, BFS
Solved
No attempts yet

Statement

In the year 2116, humans can no longer compete with AI. AI surpasses humans in strength, agility, creativity, thinking, problem solving, and even humanity. AI manages the entire Earth, and humanity lost its place as the master of the planet long ago. The one consolation is that AI does not treat humans with hostility, and thanks to the technology AI has built, everyone can enjoy unlimited resources and live the life of a wealthy idler that people a century ago dreamed of. Most humans are satisfied with the current situation and spend their time playing and eating, having given up on progress, but some humans organize a resistance to fight against AI and restore humanity's glory.

The resistance is looking for an event in which they have a chance against AI. They want to challenge AI at such an event and prove to all humanity the spirit of challenge and the greatness of humans. The resistance leadership held a meeting lasting 12 hours to find an event in which they have a chance against AI. At the meeting, many ideas came up, including algorithm problem-solving contests, rock-paper-scissors-lightning-devil-dragon-water-air-boss-sponge-wolf-tree-human-snake, Catch Mind, marble flicking, StarCraft, the poop-dodging game, Strawberry 2-bit, the strawberry-watermelon-carrot-melon game, writing contests, and sketching contests, but not a single event appeared to give even a 0.01% chance.

As everyone was discouraged, someone looked through history books and found an event in which humans have a chance against AI. It was the Go match between Lee Sedol and AlphaGo exactly 100 years earlier. Of course, AlphaGo has kept improving since then, so there is no chance in Go itself, but in a variant of Go called Baduk2, they judged that humans have a chance against AI, just as Lee Sedol won one set against AlphaGo.

The rules of Baduk2 are almost the same as Go, except that the two players do not alternate placing one stone each but place two stones each. For convenience of description, call a set of same-colored stones adjacent up, down, left, and right a group. In the board below, there are 3 black groups and 3 white groups.

In Baduk2, as in ordinary Go, you can kill trapped stones by completely surrounding the opponent's group with your stones. A group being completely surrounded is equivalent to there being no stone in the group adjacent to an empty cell.


Also, in Baduk2 you can place a stone on any empty cell. Even if it is surrounded by the opponent's stones and would be self-captured, it does not matter. Consider the following situation.

If White plays on either red cell, the connected group becomes surrounded by black stones, so under the original rules of Go this is a self-capture for White, but in Baduk2 it does not matter, and White can play on the two red cells to kill the group containing 8 black stones.

The resistance sent a challenge to AI for Baduk2, and AI surprisingly accepted it readily. Now, on March 9, 2116, the resistance begins the Baduk2 match with humanity's pride at stake. You are given the task of writing a program to help humanity win by placing 2 stones on the current board to kill as many opposing stones as possible. With humanity's honor at stake, write a program that, given the current board, finds the maximum number of opposing stones that can be killed by placing 2 stones.

Input

The first line gives N (3 ≤ N ≤ 20) and M (3 ≤ M ≤ 20), the number of rows and the number of columns of the board, separated by a single space. The next N lines each give M integers representing each row of the array, separated by single spaces. Each cell contains 0, 1, or 2. 0 means an empty cell, 1 means my stone, and 2 means the opponent's stone. It is guaranteed that there are at least 2 empty cells and that currently neither player has a group completely surrounded by the opponent's stones.

Output

On the first line, print the maximum number of opposing stones that can be killed by placing 2 stones on the current board.

Hint

You do not need to consider whether the current board shape can appear during an actual Baduk2 match.

Examples5

  1. Example 1

    Input
    3 4
2 0 0 0
0 0 0 0
0 0 0 2
    Expected output
    1

  2. Example 2

    Input
    5 4
0 0 0 0
0 2 2 0
0 2 0 0
2 2 0 0
2 2 0 0
    Expected output
    0

  3. Example 3

    Input
    8 4
0 0 2 0
0 1 2 2
0 0 1 1
2 0 0 0
0 1 0 0
2 0 1 0
2 0 0 0
0 0 0 0
    Expected output
    3

  4. Example 4

    Input
    3 3
2 2 2
2 2 2
0 2 0
    Expected output
    7

  5. Example 5

    Input
    8 6
0 0 1 2 2 2
0 0 1 2 2 2
0 1 1 0 2 2
1 2 2 0 1 1
1 2 2 1 0 0
1 2 1 0 2 0
1 1 0 0 0 1
0 1 0 0 0 0
    Expected output
    13