# Maximum Size solution – Chef is playing an easier variation of the board game ‘Risk’ with his friend Mike 2021

## Maximum Size solution

Chef is playing an easier variation of the board game ‘Risk’ with his friend Mike. There is an NMN∗M grid, depicting the world map. Each cell of the grid is either 11 or 00 where 11 denotes that there is land on this cell, while 00 denotes water.

In a turn, a player can capture an uncaptured cell that has land, and keep capturing neighbouring cells that share a side with it if they are on land. A cell once captured by a player can’t be captured again by another player. The game continues till no uncaptured cell has land. Each player wants to be in control of as many cells of land as possible in total when the game finishes. Find the maximum number of cells of land that Chef can capture if he plays second, and both players play optimally.

### Input: Maximum Size solution

• First line will contain TT, number of testcases. Then the testcases follow.
• Each testcase contains N+1N+1 lines of input.
• First line will contain 22 space separated integers NN and MM denoting the size of the grid.
• Each of the next NN lines contains a binary string of length MM depicting the map.

### Output: Maximum Size solution

For each testcase, output in a single line answer to the problem.

### Constraints : Maximum Size solution

• 1N,M1051≤N,M≤105
• Each character in the grid is either 00 or 11
• There’s atleast 11 land on the grid
• Sum of NMN∗M over all testcases is almost 106106.

### Sample Input: Maximum Size solution

3
4 4
1001
0110
0110
1001
2 2
11
11
3 3
100
010
001


### Sample Output: Maximum Size solution

2
0
1


### Explanation: Maximum Size solution

In test case 1, if both players play optimally, it takes 55 steps to finish the game:

Step 1: First Mike chooses the cells {(2,2),(2,3),(3,2),(3,3)}{(2,2),(2,3),(3,2),(3,3)} adding 44 to his score.

Step 2: Second Chef chooses the cell {(1,1)}{(1,1)} adding 11 to his score.

Step 3: Next Mike chooses the cell {(1,4)}{(1,4)} adding 11 to his score.

Step 4: Next Chef chooses the cell {(4,1)}{(4,1)} adding 11 to his score.

Step 5: Finally, Mike chooses the cell {(4,4)}{(4,4)} adding 11 to his score.

Hence total score of Chef is 1+1=21+1=2.

## C++

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
#define lld long double
#define vc vector<ll>
#define pb push_back
#define all(a) a.begin(),a.end()
const ll MOD=(1e9 +7);
const ll inf=(1000000000000000000);
typedef pair<ll,ll>pairs;
ll power(ll a, ll b){ll res=1;a=a%MOD;while(b>0){if(b&1){res=(res*a)%MOD;b--;}a=(a*a)%MOD;b>>=1;}
return res;}
vector<vc>a,vis;
ll dfs(ll i,ll j){
vis[i][j]=1;
ll cnt=1;
if(!vis[i+1][j]&&a[i+1][j])
cnt+=dfs(i+1,j);
if(!vis[i-1][j]&&a[i-1][j])
cnt+=dfs(i-1,j);
if(!vis[i][j+1]&&a[i][j+1])
cnt+=dfs(i,j+1);
if(!vis[i][j-1]&&a[i][j-1])
cnt+=dfs(i,j-1);
return cnt;
}
int main() {
//check for possible RTE, n=1,0;
std::ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
ll t,n,i,j,k,c,f;
cin>>t;
while(t--){
ll m;
cin>>n>>m;
a.resize(n+2,vc(m+2));
vis.resize(n+2,vc(m+2));
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
char ch;
cin>>ch;
a[i][j]=ch-'0';
}
}
vc cnt;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i][j]&&!vis[i][j])
cnt.pb(dfs(i,j));
}
}
sort(all(cnt),greater<ll>());
ll sum=0;
for(i=1;i<cnt.size();i+=2)
sum+=cnt[i];

cout<<sum<<"\n";
a.clear();vis.clear();
}
return 0;
}

## Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
StringBuilder sb=new StringBuilder();
while(t-->0)
{
int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]);
int i,j;
boolean g[][]=new boolean[n][m],vis[][]=new boolean[n][m];
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
if(c[j]=='1') g[i][j]=true;
}

ArrayList<Integer> land=new ArrayList<>();
int dir[][]={{-1,0},{0,-1},{1,0},{0,1}};
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(!vis[i][j] && g[i][j])
{
vis[i][j]=true;
int sz=0;
while(!qx.isEmpty())
{
int px=qx.poll(),py=qy.poll();
sz++;
for(int d[]:dir)
{
int tx=px+d[0],ty=py+d[1];
if(tx<0 || tx>=n || ty<0 || ty>=m || vis[tx][ty] || !g[tx][ty]) continue;
vis[tx][ty]=true;
}
}
}
Collections.sort(land,Collections.reverseOrder());
int ans=0;
for(i=1;i<land.size();i+=2) ans+=land.get(i);
sb.append(ans+"\n");
}
System.out.print(sb);
}
}

## Python

# Author: Udit "luctivud" Gupta @ https://www.linkedin.com/in/udit-gupta-1b7863135/ #

import math; from collections import *
import sys; from functools import reduce
import time; from itertools import groupby

sys.setrecursionlimit(10**6)

# def input() : return sys.stdin.readline()
def get_ints() : return map(int, input().strip().split())
def get_list() : return list(get_ints())
def get_string() : return list(input().strip().split())
def printxsp(*args) : return print(*args, end="")
def printsp(*args) : return print(*args, end=" ")

DIRECTIONS = [(+0, +1), (+0, -1), (+1, +0), (-1, -0)]
NEIGHBOURS = [(-1, -1), (-1, +0), (-1, +1), (+0, -1),\
(+1, +1), (+1, +0), (+1, -1), (+0, +1)]

# MAIN >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

def isvalid(i, j):
global n
global m
return i >=0 and j >= 0 and i < n and j < m

def dfs(i, j, arr):
global sz
global visited
if visited[i][j] or arr[i][j] == '0':
return
visited[i][j] = True
sz += 1
for xx, yy in DIRECTIONS:
if isvalid(i+xx, j+yy):
dfs(i+xx, j+yy, arr)

for _test_ in range(int(input())):
n, m = get_ints()
arr = []
for _ in range(n):
arr.append(input())
lands = []
visited = [[False for y in range(m)] for x in range(n)]
for i in range(n):
for j in range(m):
if not visited[i][j] and arr[i][j] == '1':
sz = 0
dfs(i, j, arr);
lands.append(sz)
lands.sort(reverse = True)
# print(lands)
ans = 0
for i in range(len(lands)//2):
ans += lands[2*i+1]
print(ans);
# print(visited)