Problem:

Problem D: Life Line

Let's play a new board game ``Life Line''.

The number of the players is greater than 1 and less than 10.

In this game, the board is a regular triangle in which many small regular triangles are arranged (See Figure l). The edges of each small triangle are of the same length. 

Figure 1: The board

The size of the board is expressed by the number of vertices on the bottom edge of the outer triangle.
For example, the size of the board in Figure 1 is 4.

At the beginning of the game, each player is assigned his own identification number between 1 and 9, and is given some stones on which his identification number is written.

Each player puts his stone in turn on one of the ``empty'' vertices. An ``empty vertex'' is a vertex that has no stone on it.

When one player puts his stone on one of the vertices during his turn, some stones might be removed from the board. The player gains points which is equal to the number of the removed stones of others, but loses points which is equal to the number of the removed stones of himself. The points of a player for a single turn is the points he gained minus the points he lost in that turn.

The conditions for removing stones are as follows:

    
 The stones on the board are divided into groups. Each group contains a set of stones whose numbers are the same and placed adjacently. That is, if the same numbered stones are placed adjacently, they belong to the same group.

    
 If none of the stones in a group is adjacent to at least one ``empty'' vertex, all the stones in that group are removed from the board.

Figure 2: The groups of stones

Figure 2 shows an example of the groups of stones.

Suppose that the turn of the player `4' comes now. If he puts his stone on the vertex shown in Figure 3a, the conditions will be satisfied to remove some groups of stones (shadowed in Figure 3b). The player gains 6 points, because the 6 stones of others are removed from the board (See Figure 3c). 

 

Figure 3a

Figure 3b

Figure 3c

As another example, suppose that the turn of the player `2' comes in Figure 2. If the player puts his stone on the vertex shown in Figure 4a, the conditions will be satisfied to remove some groups of stones (shadowed in Figure 4b). The player gains 4 points, because the 4 stones of others are removed. But, at the same time, he loses 3 points, because his 3 stones are removed. As the result, the player's points of this turn is 4 - 3 = 1 (See Figure 4c).

Figure 4a

Figure 4b

Figure 4c

When each player puts all of his stones on the board, the game is over. The total score of a player is the summation of the points of all of his turns.

Your job is to write a program that tells you the maximum points a player can get (i.e., the points he gains - the points he loses) in his current turn. 

Input

The input consists of multiple data. Each data represents the state of the board of the game still in progress.

The format of each data is as follows.

  N C

          S1,1
       S2,1  S2,2
    S3,1 S3,2 S3,3
          ...
  SN,1    ...    SN,N

N is the size of the board (3 ≤ N ≤ 10).

C is the identification number of the player whose turn comes now (1 ≤ C ≤ 9) . That is, your program must calculate his points in this turn.

Si,j is the state of the vertex on the board (0  ≤ Si,j ≤ 9) . If the value of Si,j is positive, it means that there is the stone numbered by Si,j there. If the value of Si,j is 0, it means that the vertex is ``empty''.

Two zeros in a line, i.e., 0 0, represents the end of the input. 

Output

For each data, the maximum points the player can get in the turn should be output, each in a separate line.

Sample Input

4 4
   2
  2 3
 1 0 4
1 1 4 0
4 5
   2
  2 3
 3 0 4
1 1 4 0
4 1
   2
  2 3
 3 0 4
1 1 4 0
4 1
   1
  1 1
 1 1 1
1 1 1 0
4 2
   1
  1 1
 1 1 1
1 1 1 0
4 1
   0
  2 2
 5 0 7
0 5 7 0
4 2
   0
  0 3
 1 0 4
0 1 0 4
4 3
   0
  3 3
 3 2 3
0 3 0 3
4 2
   0
  3 3
 3 2 3
0 3 0 3
6 1
     1
    1 2
   1 1 0
  6 7 6 8
 0 7 6 8 2
6 6 7 2 2 0
5 9
    0
   0 0
  0 0 0
 0 0 0 0
0 0 0 0 0
5 3
    3
   3 2
  4 3 2
 4 4 0 3
3 3 3 0 3
0 0

Output for the Sample Input

6
5
1
-10
8
-1
0
1
-1
5
0
5



Sample input:
4 4
   2
  2 3
 1 0 4
1 1 4 0
4 5
   2
  2 3
 3 0 4
1 1 4 0
4 1
   2
  2 3
 3 0 4
1 1 4 0
4 1
   1
  1 1
 1 1 1
1 1 1 0
4 2
   1
  1 1
 1 1 1
1 1 1 0
4 1
   0
  2 2
 5 0 7
0 5 7 0
4 2
   0
  0 3
 1 0 4
0 1 0 4
4 3
   0
  3 3
 3 2 3
0 3 0 3
4 2
   0
  3 3
 3 2 3
0 3 0 3
6 1
     1
    1 2
   1 1 0
  6 7 6 8
 0 7 6 8 2
6 6 7 2 2 0
5 9
    0
   0 0
  0 0 0
 0 0 0 0
0 0 0 0 0
5 3
    3
   3 2
  4 3 2
 4 4 0 3
3 3 3 0 3
0 0


Sample output:
6
5
1
-10
8
-1
0
1
-1
5
0
5

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    def f(n,m):
        a = [[-1]*(n+3)] + [[-1] + LI() + [-1]*2 for _ in range(n)] + [[-1]*(n+3)]
        aa = [c[:] for c in a]
        d = collections.defaultdict(int)
        def _f(i,j,c):
            if a[i][j] == 0:
                return (0, set([(i,j)]))
            if a[i][j] != c:
                return (0,set())
            a[i][j] = -1
            r = [1, set()]
            for di,dj in [(-1,-1),(-1,0),(0,-1),(0,1),(1,0),(1,1)]:
                t = _f(i+di,j+dj,c)
                r[0] += t[0]
                r[1] |= t[1]
            # print('_f',i,j,c,r)
            return tuple(r)
        for i in range(1,n+1):
            for j in range(1,i+1):
                if a[i][j] != m:
                    continue
                c,s = _f(i,j,a[i][j])
                if len(s) == 1:
                    d[list(s)[0]] = -1
        a = aa
        aa = [c[:] for c in a]
        for i in range(1,n+1):
            for j in range(1,i+1):
                if a[i][j] != 0:
                    continue
                if (i,j) in d:
                    continue
                tf = True
                for di,dj in [(-1,-1),(-1,0),(0,-1),(0,1),(1,0),(1,1)]:
                    if a[i+di][j+dj] in [0,m]:
                        tf = False
                        break
                if tf:
                    d[(i,j)] = -1
                else:
                    d[(i,j)] = 0

        ts = collections.defaultdict(set)
        for i in range(1,n+1):
            for j in range(1,i+1):
                if a[i][j] != m:
                    continue
                cc = a[i][j]
                sf = -1 if a[i][j] == m else 1
                c,s = _f(i,j,a[i][j])
                # print('res',i,j,c,s,sf,len(s))
                if len(s) > 1:
                    for sc in s:
                        ts[sc].add(cc)
                        d[sc] = 0

        a = aa
        # print(d)
        # print('\n'.join("\t".join(map(str,_)) for _ in a))
        for i in range(1,n+1):
            for j in range(1,i+1):
                if a[i][j] < 1:
                    continue
                cc = a[i][j]
                sf = -1 if a[i][j] == m else 1
                c,s = _f(i,j,a[i][j])
                # print('res',i,j,c,s,sf,len(s))
                if len(s) == 1 and cc not in ts[list(s)[0]]:
                    if sf == 1:
                        d[list(s)[0]] += c * sf
                    else:
                        d[list(s)[0]] += c * sf
                # print('\n'.join("\t".join(map(str,_)) for _ in a))
        # print('\n'.join("\t".join(map(str,_)) for _ in a))
        # print(d)
        if len(d) == 0:
            return 0
        return max(d.values())

    while True:
        n,m = LI()
        if n == 0 and m == 0:
            break
        rr.append(f(n,m))

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    N, C = map(int, raw_input().split())
    if N == 0:
        break
    S = []
    for loop in range(N):
        lst = map(int, raw_input().split())
        S.append(lst)
    used = {}
    def func(x, y, c):
        if x < 0 or x > y or y >= N:
            return []
        if (x, y) in used:
            return []
        used[(x, y)] = 1
        if S[y][x] == 0:
            return [(x, y)]
        if S[y][x] != c:
            return []
        lst = []
        pos = [[x - 1, y], [x + 1, y], [x - 1, y - 1], [x, y - 1], [x, y + 1], [x + 1, y + 1]]
        for p in pos:
            p += [c]
            ret = func(*p)
            if ret:
                lst += ret
        return lst
    ans = -10000
    for y in range(N):
        for x in range(y + 1):
            if S[y][x] == 0:
                dum = S[y][x]
                S[y][x] = C
                ret = []
                for i in range(N):
                    for j in range(i + 1):
                        if S[i][j] != 0:
                            used = {}
                            if len(func(j, i, S[i][j])) == 0:
                                ret.append(S[i][j])
                S[y][x] = dum
                score = 0
                for num in ret:
                    if num == C:
                        score -= 1
                    else:
                        score += 1
                ans = max(ans, score)
    print ans

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self, N):
        self.N = N
        self.arr = [ [ None for _ in range(N) ] for _ in range(N) ]

    def duplicate(self):
        newTree = Tree(self.N)
        for i in range(N):
            row = self.arr[i]
            newTree.arr[i] = row[:]
        return newTree

    def setVal(self, row, col, val):
        self.arr[row][col] = val

    def setGroup(self, grp, val):
        for cell in grp:
            self.arr[cell[0]][cell[1]] = val

    def getCellPoints(self, row, col, C):
        val = self.arr[row][col]
        if val == 0 or val == -1:
            return 0

        grp = set()
        self.getGroup(row, col, val, grp)

        isSafe = False
        for cell in grp:
            if self.hasZeroNeighbor(cell[0], cell[1]):
                isSafe = True
                break

        self.setGroup(grp, -1)

        if isSafe:
            return 0
        
        if val == C:
            return len(grp) * -1
        
        else:
            return len(grp)

    def calcCellPoints(self, row, col, C):
        neighbors = self.getNeighbors(row, col)

        # print("\nConsidering placing stone in", (row, col), "...")
        # print("These are the neighbors:")
        # for x in neighbors:
        #     print(x)

        points = self.getCellPoints(row, col, C)

        for nb in neighbors:
            points += self.getCellPoints(nb[0], nb[1], C)

        return points

    def getNeighbors(self, row, col):
        neighbors = []
        if row < self.N - 1:
            neighbors.append( (row + 1, col) )
            neighbors.append( (row + 1, col + 1) )
        if col <= row - 1:
            neighbors.append( (row, col + 1) )
            neighbors.append( (row - 1, col) )
        if col > 0:
            neighbors.append( (row, col - 1) )
            neighbors.append( (row - 1, col - 1) )
        return neighbors

    def hasZeroNeighbor(self, row, col):
        neighbors = self.getNeighbors(row, col)
        for nb in neighbors:
            if self.arr[nb[0]][nb[1]] == 0:
                return True
        return False

    def getGroup(self, row, col, v, groupCells):
        if (row, col) in groupCells:
            return
        if self.arr[row][col] == v:
            groupCells.add((row, col))
            neighbors = self.getNeighbors(row, col)
            for nb in neighbors:
                self.getGroup(nb[0], nb[1], v, groupCells)

if __name__ == '__main__':
    while True:
        N, C = list(map(int, input().strip().split()))
        if N == 0 and C == 0:
            break

        tree = Tree(N)
        emptySpots = []

        for i in range(N):
            arr = [ int(x) for x in list(filter(lambda x: x != '', \
                input().strip().split(' '))) ]
            for j in range(len(arr)):
                tree.setVal(i, j, arr[j])
                if arr[j] == 0:
                    emptySpots.append( (i, j) )

        maxPoints = -999999999
        for spot in emptySpots:
            newTree = tree.duplicate()
            newTree.setVal(spot[0], spot[1], C)
            maxPoints = max(maxPoints, newTree.calcCellPoints(spot[0], spot[1], C))
        
        print(maxPoints)