BOJ - 11559 - Puyo Puyo

Updated:

import sys
from collections import deque

N, M = 12, 6
Field = [list(input().strip()) for _ in range(N)]

def BFS(i, j, puyo, check):
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

dq = deque()
block = [[i, j]]
dq.append((i, j))
check[i][j] = True

while dq:
x, y = dq.popleft()
for step in range(4):
nx, ny = x + dx[step], y + dy[step]
if nx < 0 or nx >= N or ny < 0 or ny >= M:
continue

if not check[nx][ny] and Field[nx][ny] == puyo:
check[nx][ny] = True
block.append([nx, ny])
dq.append((nx, ny))

if len(block) >= 4:
for x, y in block:
Field[x][y] = '.'
return True

else:
return False

def PuyoFall():
for i in range(M):
for j in range(N - 1, -1, -1):
if Field[j][i] == '.':
continue
for k in range(N - 1, j - 1, -1):
if Field[k][i] == '.':
Field[k][i] = Field[j][i]
Field[j][i] = '.'

def PuyoCrash():
isCrash = False

check = [[False for _ in range(M)] for _ in range(N)]
for i in range(N - 1, -1, -1):
for j in range(M - 1, -1, -1):
if check[i][j] or Field[i][j] == '.':
continue

if BFS(i, j, Field[i][j], check):
isCrash = True

return isCrash

def solution():
ret = 0

while PuyoCrash():
PuyoFall()
ret += 1

print(ret)

solution()

https://www.acmicpc.net/problem/11559

Categories:

Updated: