The designers at Gazillion Games Inc. have come up with a new, relatively simple game called "Stake Your Claim". Two players – 0 and 1 – initially select two values n and m and an n × n board is created with m 0's and m 1's randomly placed on the board. Starting with player 0, each player puts his/her number in one of the empty squares on the board. After the board is filled, each player's score is equal to the largest connected region on the board filled with that player's number (where a connected region is one where for any two squares in the region a path exists consisting of only N/S/E/W moves). The player with the highest score wins, and is awarded the difference between his/her score and the score of the other player. Two examples of finished games are shown below, with the largest connected regions for each player outlined. Note in the second example that the two sections with 2 0's each are not connected.
In order to test how good this game is, the gang at Gazillion has hired you to write a program which can play the game. Specifically, given any starting configuration, they would like a program to determine the best move for the current player, i.e., the score which maximizes the points awarded to that player (or minimizes those awarded to the player's opponent).
4
01.1
00..
.01.
...1
4
0.01
0.01
1..0
.1..
0
(1,2) 2
(2,2) -1