"""
출처:프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/84021
"""
# 풀이 과정
"""
조건:
1회에 1번
조각 회전가능
뒤집기 불가능 

목표:
채울 수 있는 최대칸을 구하여라 

생각방향:모양이 들어맞아야 인접한 곳이 비는 일이 없어짐에 따라 빈 곳과 테이블을 비교해야한다

회전하는 방법에 대한 아이디어 생각 > 회전변환

닮음의 원칙 응용 생각 고민

# 양쪽 맵의 도형 좌표들을 모두 모은 후 리스트로 모은 후 두 맵 중 하나의 좌표를 하나씩 팝 한 후 
회전변환 후 도형 중 가장 작은 점을 찾은 후 평행 이동 시켰을 때 같은 도형이라면 집합상 동일하다는 점을 체크 후 구하기 
"""

v = []

# 보드 도형
board = []

# 테이블 도형
check = []

from collections import deque
import copy


def find(i, j, g, s):
    global v_baord, v_table, board, check

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    new = []

    q = deque([[i, j]])

    while q:
        a, b = q.popleft()
        v[a][b] = True
        new.append([a, b])

        for k, t in zip(dx, dy):
            if 0 <= a + k < len(g) and 0 <= b + t < len(g[0]):
                if v[a + k][b + t] == False and s == "board":
                    if g[a + k][b + t] == 0:
                        q.append([a + k, b + t])
                        v[a + k][b + t] = True
                elif v[a + k][b + t] == False and s == "table":
                    if g[a + k][b + t] == 1:
                        q.append([a + k, b + t])
                        v[a + k][b + t] = True
                        # print(a+k,b+t)

    # print(new,"new",s)

    x = copy.deepcopy(new)

    # if s=="board":
    #     check.append(x)
    # else:
    #     board.append(x)

    return x


def solution(game_board, table):
    global check, board, v

    g = game_board
    t = table

    # 행 길이
    m = len(table)

    # 열 길이
    n = len(table[0])

    # 방문 기록
    v = [[False] * n for _ in range(m)]

    s = "board"

    # 보드의 빈공간 도형 찾기
    for i in range(m):
        for j in range(n):
            if g[i][j] == 0 and v[i][j] == False:
                plus = find(i, j, g, s)
                board.append(plus)

    # 보드 내 도형을 구한 후 초기화
    v = [[False] * n for _ in range(m)]

    s = "table"

    # 테이블의 도형 찾기
    for i in range(m):
        for j in range(n):
            if t[i][j] == 1 and v[i][j] == False:
                # print(i,j,"table 도형 찾기 시작점")
                plus = find(i, j, t, s)
                # print(check,"find 후 check")
                check.append(plus)

    # 테이블의 도형을 하나씩 뽑아낸 후 모든 좌표를 90도 회전변환 후 닮음 여부 체크
    result = 0  # 채워질때마다 추가

    # board=deque(board)

    # check:테이블 도형 board: 보드 도형

    board = deque(board)

    count = len(board)

    # print(check,"table 도형",board,"보드 도형")

    while count > 0:
        o = board.popleft()
        o.sort()
        board.append(o)
        count -= 1

    while check:
        k = check.pop()
        new = []
        k.sort()
        new.append(k)
        one = []  # 90도
        two = []  # 180도
        three = []  # 270도

        for x, y in k:
            one.append([-y, x])
            two.append([-x, -y])
            three.append([y, -x])

        one.sort()
        two.sort()
        three.sort()
        new.append(one)
        new.append(two)
        new.append(three)

        new_board = []

        while board:
            figure = board.popleft()

            # 꼭짓점의 개수 체크
            if len(new[0]) == len(figure):
                flag = False
                # 0도~270도
                for i in range(4):
                    num1, num2 = (new[i][0][0] - figure[0][0]), (new[i][0][1] - figure[0][1])

                    for j in range(len(figure)):
                        if (new[i][j][0] - figure[j][0]) != num1 or (new[i][j][1] - figure[j][1]) != num2:
                            break
                    else:
                        # 같은 도형
                        flag = True
                        # print(new[0],i,"figure",figure,num1,num2)
                        result += len(new[0])
                        break
            else:
                new_board.append(figure)
                continue

            if flag == False:
                new_board.append(figure)

            elif flag == True:
                break

        board += new_board

    return result