Problem:


J: Tiles are Colorful

ICPC で良い成績を収めるには修行が欠かせない．うさぎは ICPC で勝ちたいので，今日も修行をすることにした．

今日の修行は，流行りのパズルをすばやく解いて，瞬発力を鍛えようというものである．今日挑戦するのは，色とりどりのタイルが並んでいてそれらを上手く消していくパズルだ

初期状態では，グリッド上のいくつかのマスにタイルが置かれている．各タイルには色がついている．プレイヤーはゲーム開始後，以下の手順で示される操作を何回も行うことができる．

タイルが置かれていないマスを 1 つ選択し，そのマスを叩く．

叩いたマスから上に順に辿っていき，タイルが置かれているマスに至ったところでそのタイルに着目する．タイルが置かれているマスがないまま盤面の端に辿り着いたら何にも着目しない．

同様の操作を叩いたマスから下・左・右方向に対して行う．最大 4 枚のタイルが着目されることになる．

着目したタイルの中で同じ色のものがあれば，それらのタイルを盤面から取り除く．同じ色のタイルの組が 2 組あれば，それら両方を取り除く．

タイルを取り除いた枚数と同じ値の得点が入る．

着目をやめる．

たとえば，以下のような状況を考えよう．タイルが置かれていないマスはピリオドで，タイルの色はアルファベット大文字で表されている．

..A.......
.......B..
..........
..B.......
..A.CC....

ここで上から 2 行目，左から 3 列目のマスを叩く操作を考える．着目することになるタイルは A , B , B の 3 枚であるから，B の 2 枚が消えて盤面は以下のようになり，2 点を得る．

..A.......
..........
..........
..........
..A.CC....

このパズルはゆっくりしていると時間切れになってしまい，盤面の一部が見えなくなりどのくらい修行が足りなかったのかがわからなくなってしまう．
各色のタイルは 2 枚ずつ置かれているが，それらをすべて消せるとは限らないので，予めプログラムに得点の最大値を計算させておきたい．

Input

M N
C1,1C1,2...C1,N
C2,1C2,2...C2,N
 ...
CM,1CM,2...CM,N

整数 M, N は盤が 縦 M &times; 横 N のマス目であることを表す．Ci, j はアルファベット大文字またはピリオド ( . ) であり，上から i 行目，左から j 列目のマスについて，アルファベット大文字の場合は置かれているタイルの色を表し，ピリオドの場合はこのマスにタイルが置かれていないことを表す．

1 ≤ M ≤ 500，1 ≤ N ≤ 500 を満たす．各アルファベット大文字は入力中に 0 個または 2 個現れる．

Output

得点の最大値を 1 行に出力せよ．

Sample Input 1

5 10
..A.......
.......B..
..........
..B.......
..A.CC....

Sample Output 1

4

Sample Input 2

3 3
ABC
D.D
CBA

Sample Output 2

4

Sample Input 3

5 7
NUTUBOR
QT.SZRQ
SANAGIP
LMDGZBM
KLKIODP

Sample Output 3

34



Sample input:
5 10
..A.......
.......B..
..........
..B.......
..A.CC....


Sample output:
4

Submission status: Wrong Answer

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**10
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():
    m,n = LI()
    a = [[c for c in S()] for _ in range(m)]
    ad = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            if a[i][j] != '.':
                ad[a[i][j]].append((i,j))
    ps = set(map(tuple,ad.values()))
    f = True
    r = 0
    while f:
        f = False
        for pa,pb in list(ps):
            i1,j1 = pa
            i2,j2 = pb
            if i1 == i2:
                ff = True
                for j in range(min(j1,j2)+1,max(j1,j2)):
                    if a[i1][j] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2
            elif j1 == j2:
                ff = True
                for i in range(min(i1,i2)+1,max(i1,i2)):
                    if a[i][j1] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2
            else:
                i,j = i1,j2
                ff = True
                for j3 in range(min(j,j2)+1,max(j,j2)):
                    if a[i][j3] != '.':
                        ff = False
                        break
                for i3 in range(min(i,i2)+1,max(i,i2)):
                    if a[i3][j] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2
                    continue
                i,j = i2,j1
                ff = True
                for j3 in range(min(j,j1)+1,max(j,j1)):
                    if a[i][j3] != '.':
                        ff = False
                        break
                for i3 in range(min(i,i1)+1,max(i,i1)):
                    if a[i3][j] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2

    return r



print(main())

Submission status: Wrong Answer

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**10
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():
    m,n = LI()
    a = [[c for c in S()] for _ in range(m)]
    ad = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            if a[i][j] != '.':
                ad[a[i][j]].append((i,j))
    ps = set(map(tuple,ad.values()))
    f = True
    r = 0
    while f:
        f = False
        for pa,pb in list(ps):
            i1,j1 = pa
            i2,j2 = pb
            if i1 == i2 and abs(j1-j2) > 1:
                ff = True
                for j in range(min(j1,j2)+1,max(j1,j2)):
                    if a[i1][j] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2
            elif j1 == j2 and abs(i1-i2) > 1:
                ff = True
                for i in range(min(i1,i2)+1,max(i1,i2)):
                    if a[i][j1] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2
            else:
                i,j = i1,j2
                ff = a[i][j] == '.'
                for j3 in range(min(j,j2)+1,max(j,j2)):
                    if a[i][j3] != '.':
                        ff = False
                        break
                for i3 in range(min(i,i2)+1,max(i,i2)):
                    if a[i3][j] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2
                    continue
                i,j = i2,j1
                ff = a[i][j] == '.'
                for j3 in range(min(j,j1)+1,max(j,j1)):
                    if a[i][j3] != '.':
                        ff = False
                        break
                for i3 in range(min(i,i1)+1,max(i,i1)):
                    if a[i3][j] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2

    return r



print(main())

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**10
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():
    m,n = LI()
    a = [[c for c in S()] for _ in range(m)]
    ad = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            if a[i][j] != '.':
                ad[a[i][j]].append((i,j))
    ps = set(map(tuple,ad.values()))
    f = True
    r = 0
    while f:
        f = False
        for pa,pb in list(ps):
            i1,j1 = pa
            i2,j2 = pb
            if i1 == i2:
                ff = abs(j1-j2) > 1
                for j in range(min(j1,j2)+1,max(j1,j2)):
                    if a[i1][j] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2
            elif j1 == j2:
                ff = abs(i1-i2) > 1
                for i in range(min(i1,i2)+1,max(i1,i2)):
                    if a[i][j1] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2
            else:
                i,j = i1,j2
                ff = a[i][j] == '.'
                for j3 in range(min(j,j1)+1,max(j,j1)):
                    if a[i][j3] != '.':
                        ff = False
                        break
                for i3 in range(min(i,i2)+1,max(i,i2)):
                    if a[i3][j] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2
                    continue

                i,j = i2,j1
                ff = a[i][j] == '.'
                for j3 in range(min(j,j2)+1,max(j,j2)):
                    if a[i][j3] != '.':
                        ff = False
                        break
                for i3 in range(min(i,i1)+1,max(i,i1)):
                    if a[i3][j] != '.':
                        ff = False
                        break
                if ff:
                    f = True
                    a[i1][j1] = '.'
                    a[i2][j2] = '.'
                    ps.remove((pa,pb))
                    r += 2

    return r



print(main())

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
mp = [input() for _ in range(h)]

points = {}
for y in range(h):
  for x in range(w):
    c = mp[y][x]
    if c != ".":
      if c not in points:
        points[c] = [(x, y)]
      else:
        points[c].append((x, y))

keys = []
preventer = {}
for c, ps in points.items():
  keys.append(c)
  p1, p2 = ps
  x1, y1 = p1
  x2, y2 = p2
  if x1 == x2:
    s = set()
    for y in range(y1 + 1, y2):
      s.add(mp[y][x1])
    preventer[c] = [s]
    continue

  if y1 == y2:
    s = set()
    for x in range(x1 + 1, x2):
      s.add(mp[y1][x])
    preventer[c] = [s]
    continue

  s1 = set()
  s2 = set()
  if x1 < x2:
    for x in range(x1 + 1, x2):
      s1.add(mp[y1][x])
    for y in range(y1, y2):
      s1.add(mp[y][x2])
    for x in range(x1, x2):
      s2.add(mp[y2][x])
    for y in range(y1 + 1, y2):
      s2.add(mp[y][x1])

  else:
    for x in range(x2, x1):
      s1.add(mp[y1][x])
    for y in range(y1 + 1, y2):
      s1.add(mp[y][x2])
    for x in range(x2 + 1, x1):
      s2.add(mp[y2][x])
    for y in range(y1 + 1, y2 + 1):
      s2.add(mp[y][x1])
  preventer[c] = [s1, s2]

removal = {".":True}
for key in keys:
  removal[key] = False
ans = 0
while True:
  remove_lst = []
  for key in keys:
    for s in preventer[key]:
      if not s:
        break
      
      for c in s:
        if not removal[c]:
          break
      else:
        removal[key] = True
        remove_lst.append(key)
        ans += 2
        break
  
  if not remove_lst:
    break

  for rem in remove_lst:
    keys.remove(rem)

print(ans)