Problem:


Problem C: コンパイル

東京大学に入学したきたまさ君はTSG(東大スーパーゲーマーズ)というサークルに入った。

このサークルは毎年、駒場祭でゲームを展示しており、きたまさ君もゲームを作成して展示することにした。

きたまさ君の作成するゲームは次のような、よくある落ち物パズルゲームである。

横6マス×縦12マスの格子状のフィールドがあり、各マスにつき1個のブロックを置くことができる。

上からブロックが2つ1組で落下してくる。ブロックには赤・緑・青・黄・紫の5色の基本ブロックとお邪魔ブロックの計6種類がある。プレイヤーはブロックを回転、横移動により操作し、落下位置を変更することができる。

落下してきたブロックがフィールドの床やほかのブロックに衝突すると、その位置にブロックが固定される。

固定されたブロックと同色のブロックが周囲4方向にある場合、それらは互いにくっつく。ただし、お邪魔ブロックは互いにくっつかない。

ブロックが4個以上くっつくと消滅し得点となる。お邪魔ブロックの周囲4方向に存在する基本ブロックが消滅すると、そのお邪魔ブロックも一緒に消滅する。ブロックの消滅は、全てのブロックの落下が終了したタイミングで同時に起こる。

ブロックの消滅により、その上にあったブロックが落下する。このブロックの落下はプレイヤーが操作できない。このとき再びブロックが4個以上くっつくと消滅し、連鎖が起きる。ただし、複数色を同時に消した場合でも、1連鎖扱いとなる。

きたまさ君はこのゲームの大部分のプログラムを書き終えたが、どうしてもブロックがくっついて消滅したときの処理を書くことが出来なかった。そこでサークルの友人であるあなたにその部分のプログラムを書いてもらうことにした。 

Input

入力は12行からなる。

入力の i 行目は長さ6の文字列からなり、その j 文字目はフィールドの上から i 行目、左から j 列目のマスの状態を表している。

マスの状態を表す文字は以下の7つのうちのいずれかである。

	
文字種類

	
R赤

	
G緑

	
B青

	
Y黄

	
P紫

	
Oお邪魔

	
.空きマス

また、入力に含まれる全てのブロックは床の上か他のブロックの上に乗っている。 

Output

入力の状態から、ルールに従ってブロックを消していった時の連鎖数を計算し、一行で出力せよ。

ブロックが一つも消えない場合は0と出力せよ。 

Notes on Test Cases

上記入力形式で複数のデータセットが与えられます。

入力の1行目にデータセットの数Tが与えられます。

各データセットに対して上記出力形式で出力を行うプログラムを作成して下さい。

Sample Input 

3
......
......
......
......
......
......
......
......
.RGB..
RGOP..
RGBPB.
RGBPP.
GBRGYP
GBRRYP
BGGRBB
BPRGYY
GGPRRY
BYPPRB
YGGGPB
GYYYPR
YRBRBR
YBRBRB
BRBRBR
BRBRBR
......
......
......
......
......
......
......
......
......
......
..OO..
..OO..

Output for Sample Input

3 
18 
0 



Sample input:
3
......
......
......
......
......
......
......
......
.RGB..
RGOP..
RGBPB.
RGBPP.
GBRGYP
GBRRYP
BGGRBB
BPRGYY
GGPRRY
BYPPRB
YGGGPB
GYYYPR
YRBRBR
YBRBRB
BRBRBR
BRBRBR
......
......
......
......
......
......
......
......
......
......
..OO..
..OO..


Sample output:
3
18
0

Submission status: Wrong Answer

Solution code:
t = int(input())
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
for _ in range(t):
  def check(x, y, lst, checked):
    checked[y][x] = False
    color = mp[y][x]
    for dx, dy in vec:
      nx, ny = x + dx, y + dy
      if color == mp[ny][nx] and checked[ny][nx] == None:
        lst.append((nx, ny))
        check(nx, ny, lst, checked)
  
  mp = [list("X" * 8)] + [list("X" + input() + "X") for _ in range(12)] + [list("X" * 8)]
  cnt = 0
  
  while True:
    checked = [[None] * 8 for _ in range(14)]
    for y in range(1, 13):
      for x in range(1, 7):
        if mp[y][x] in ("O", ".", "X"):
          checked[y][x] = False
        elif checked[y][x] == None:
          lst = [(x, y)]
          check(x, y, lst, checked)
          length = len(lst)
          if length < 4:continue
          for nx, ny in lst:
            checked[ny][nx] = True
  
    if not any(any(lst) for lst in checked):
      break
    
    for y in range(1, 13):
      for x in range(1, 7):
        if mp[y][x] == "O":
          for dx, dy in vec:
            nx, ny = x + dx, y + dy
            if mp[ny][nx] != "0" and checked[ny][nx]:
              checked[y][x] = True
    
    for y in range(1, 13):
      for x in range(1, 7):
        if checked[y][x]:
          mp[y][x] = "."
  
    for x in range(1, 7):
      s = ""
      for y in range(12, 0, -1):
        s = mp[y][x] + s
      s = s.replace(".", "")
      s = "." * (12 - len(s)) + s
      for y in range(12, 0, -1):
        mp[y][x] = s[y - 1]
  
    cnt += 1
  
  print(cnt)

Submission status: Accepted

Solution code:
t = int(input())
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
for _ in range(t):
  def check(x, y, lst, checked):
    checked[y][x] = False
    color = mp[y][x]
    for dx, dy in vec:
      nx, ny = x + dx, y + dy
      if color == mp[ny][nx] and checked[ny][nx] == None:
        lst.append((nx, ny))
        check(nx, ny, lst, checked)
  
  mp = [list("X" * 8)] + [list("X" + input() + "X") for _ in range(12)] + [list("X" * 8)]
  cnt = 0
  
  while True:
    checked = [[None] * 8 for _ in range(14)]
    for y in range(1, 13):
      for x in range(1, 7):
        if mp[y][x] in ("O", ".", "X"):
          checked[y][x] = False
        elif checked[y][x] == None:
          lst = [(x, y)]
          check(x, y, lst, checked)
          length = len(lst)
          if length < 4:continue
          for nx, ny in lst:
            checked[ny][nx] = True
  
    if not any(any(lst) for lst in checked):
      break
    
    for y in range(1, 13):
      for x in range(1, 7):
        if mp[y][x] == "O":
          for dx, dy in vec:
            nx, ny = x + dx, y + dy
            if mp[ny][nx] != "O" and checked[ny][nx]:
              checked[y][x] = True
    
    for y in range(1, 13):
      for x in range(1, 7):
        if checked[y][x]:
          mp[y][x] = "."
  
    for x in range(1, 7):
      s = ""
      for y in range(12, 0, -1):
        s = mp[y][x] + s
      s = s.replace(".", "")
      s = "." * (12 - len(s)) + s
      for y in range(12, 0, -1):
        mp[y][x] = s[y - 1]
  
    cnt += 1
  
  print(cnt)

Submission status: Accepted

Solution code:
def kesu(x, s, c, h):
    global n
    if (x[0] - 1, x[1]) not in s and a[x[0] - 1][x[1]] == c:
        s.add((x[0] - 1, x[1]))
        kesu((x[0] - 1, x[1]), s, c, h + 1) 
    if (x[0] + 1, x[1]) not in s and a[x[0] + 1][x[1]] == c:
        s.add((x[0] + 1, x[1]))
        kesu((x[0] + 1, x[1]), s, c, h + 1) 
    if (x[0], x[1] - 1) not in s and a[x[0]][x[1] - 1] == c:
        s.add((x[0], x[1] - 1))
        kesu((x[0], x[1] - 1), s, c, h + 1) 
    if (x[0], x[1] + 1) not in s and a[x[0]][x[1] + 1] == c:
        s.add((x[0], x[1] + 1))
        kesu((x[0], x[1] + 1), s, c, h + 1)
    if h == 0 and len(s) > 3:
        for i in s:a[i[0]][i[1]] = "."
        n |= s

def otosu():
    for i in range(1,12)[::-1]:
        for j in range(1, 7):
            n = 0
            while i + n < 12:
                if a[i + n][j] != "." and a[i + n + 1][j] == ".":
                    a[i + n][j], a[i + n + 1][j] = a[i + n + 1][j], a[i + n][j]
                    n += 1
                else:break
                

for _ in range(int(input())):
    a = [["." for _ in range(8)]] + [["."] + list(input()) + ["."] for _ in range(12)] + [["." for _ in range(8)]]
    rensa = 0
    while 1:
        n = set()
        for i in range(1, 13):
            for j in range(1, 7):
                if a[i][j] in ("RGBYP"):
                    kesu((i, j), set(), a[i][j], 0)
        if n == set():break
        else:
            rensa += 1
            for i in range(1, 13):
                for j in range(1, 7):
                    if a[i][j] == "O":
                        if (i - 1, j) in n or (i + 1, j) in n or (i, j - 1) in n or (i, j + 1) in n:a[i][j] = "."
        otosu()
    print(rensa)

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

LOOP = input()
for loop in range(LOOP):
    puyo = []
    for i in range(12):
        puyo.append(list(raw_input()))
    
    for cnt in range(20):
        used = [[False] * 6 for i in range(12)]
        def func(y, x, c):
            if y < 0 or x < 0 or y >= 12 or x >= 6:
                return 0
            if puyo[y][x] != c or used[y][x]:
                return 0
            used[y][x] = True
            ret = 1
            ret += func(y - 1, x, c)
            ret += func(y + 1, x, c)
            ret += func(y, x - 1, c)
            ret += func(y, x + 1, c)
            return ret

        def erase(y, x, c):
            if y < 0 or x < 0 or y >= 12 or x >= 6:
                return
            if puyo[y][x] == 'O':
                puyo[y][x] = '.'
                return
            if puyo[y][x] != c:
                return
            puyo[y][x] = '.'
            erase(y - 1, x, c)
            erase(y + 1, x, c)
            erase(y, x - 1, c)
            erase(y, x + 1, c)

        flag = True
        for i in range(12):
            for j in range(6):
                if puyo[i][j] in "RGBYP":
                    num = func(i, j, puyo[i][j])
                    if num >= 4:
                        flag = False
                        erase(i, j, puyo[i][j])
        for t in range(50):
            for i in range(1, 12):
                for j in range(6):
                    if puyo[i][j] == '.':
                        puyo[i][j], puyo[i - 1][j] = puyo[i - 1][j], puyo[i][j]
        if flag:
            print cnt
            break