This page is still under construction.

Parts of this page are still being built. What you see may change.

Baaaaaaaaaduk2 (Hard)

Time limit2sMemory limit512 MB

Summary
Given an N by M Baduk board, place two of your stones on empty cells so that the total number of opponent stones in fully surrounded groups is maximized.
Level

Medium7 of 10

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

Problem

In the year 2116, humans can no longer match AI. AI beats humans in strength, reflexes, creativity, thinking, problem solving, and even in humanity. AI manages the entire Earth, and humanity lost its place as the master of the planet long ago. The fortunate part is that AI does not treat humans with hostility, and thanks to the dazzling technological advances AI has built, everyone can use unlimited resources and enjoy the life of a wealthy idler that people a century ago dreamed of. Most humans are content with the current situation and spend their time playing and eating, having given up on progress, but some humans have organized a resistance and are fighting AI to restore humanity's glory.

The resistance is looking for a game in which they have a chance against AI. They want to challenge AI at such a game and prove to all humanity their spirit of challenge and human greatness. The resistance leadership held a meeting lasting 12 hours to find a game in which they have a chance against AI. In the meeting, many ideas came up, such as an algorithm problem-solving contest, rock-paper-scissors-lightning-devil-dragon-water-air-boss-sponge-wolf-tree-human-snake game, Catch Mind, egg-fighting, StarCraft, the poop-dodging game, Strawberry 2-Beat, the strawberry-watermelon-carrot-melon game, a writing contest, and a sketching contest, but none of them looked like they had even a 0.01% chance.

While everyone was discouraged, someone looked through history books and found a game 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, but in Baduk2, a game with modified Go rules, 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 two. For convenience, 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 an opponent's group with your own stones. A group being completely surrounded is equivalent to no stone in that group being adjacent to an empty cell.

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

For white, placing a stone on either red cell would cause the connected group to be surrounded by black stones, so under ordinary Go rules both are self-capture points, but in Baduk2 it does not matter: white can place stones on the two red cells and kill the group containing 8 black stones.

The resistance sent AI a challenge to Baduk2, and AI unexpectedly accepted it. Now, on March 9, 2116, the resistance begins the Baduk2 match with humanity's pride on the line. You are given the task of writing a program to help humanity win, one that places two stones on the current board so as to kill as many opponent stones as possible. Write a program that, given the current board, finds the maximum number of opponent stones that can be killed by placing two stones.

Input

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

Output

Print the maximum number of opponent stones that can be killed by placing two stones on the current board.

Hint

You do not need to consider whether the current board's shape could occur 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