ABC218 C - Shapes에서 배운

시간 가득 찼지만 time out.



납득한 것을 콘테스트 후에 입력했지만 WA였다.

개선점 1 배열 회전에 Append는 적합하지 않음

rotated_bad.py

def one(S,T):
    lis = []
    for _ in range(N):
        lis.append([])

    for w in range(N):
        for h in range(N-1,-1,-1):
            lis[w].append(T[h][w])

    S = make(S)
    lis = make(lis)
    #print(S)
    #print(lis)
    try:
        if check(S,lis):
            return True
    except:
        pass

잘 썼다, 나.
append를 사용하는 경우 4회전, 각각의 경우에
def를 준비해야하며 비효율적입니다.

지식자의 지혜를 빌리면
공란의 배열을 준비해, S(orT) 를 90 도 회전시켜 대입하는 함수가 있으면
함수는 하나로 끝나는 것을 알았다.

rotated_good.py

def rotated(S):
    lis = [[" "] * N for _ in range(N)]
    for h in range(N):
        for w in range(N):
           lis[w][N-1-h] = S[h][w]
           #lis[i][j] = S[j][N-1-i]

    #for h in range(N):
    #    print("".join(lis[h]))
    #print()
    return lis

개선점 2 평행 이동이라고 하면 솔직하게 평행 이동하자

처음 생각한 것은
도형을 포함한 최소 사각형을 자르고,
S와 T로 수행하고 비교했다.
그러나 Wa x 5가 남아있었습니다.

평행 이동의 이미지, 이하의 적선의 교점을 왼쪽 상단에 가져간다.
나머지 셀은 "."이며 N x N 구성.



우선. . 빨간색 선의 교차점을 찾습니다.
즉, "#"가 배치되어 있는 최소의 (i, j)를 찾는다.

make.py

def make(S,T):

    s_min_i = N
    s_min_j = N
    t_min_i = N
    t_min_j = N

    for h in range(N):
        for w in range(N):
            if S[h][w] == "#":
                s_min_i = min(s_min_i,h)
                s_min_j = min(s_min_j,w)
            if T[h][w] == "#":
                t_min_i = min(t_min_i,h)
                t_min_j = min(t_min_j,w)

또한, 너무 많은 프레임에는 "."이지만,
T, S를 비교한다.

make.py

def make(S,T):

    s_min_i = N
    s_min_j = N
    t_min_i = N
    t_min_j = N

    for h in range(N):
        for w in range(N):
            if S[h][w] == "#":
                s_min_i = min(s_min_i,h)
                s_min_j = min(s_min_j,w)
            if T[h][w] == "#":
                t_min_i = min(t_min_i,h)
                t_min_j = min(t_min_j,w)

    Schar = ""
    Tchar = ""
    for h in range(N):
        for w in range(N):
            si = s_min_i + h
            sj = s_min_j + w
            if (si < N and sj < N):
                Schar = S[si][sj]
            else:
                Schar = "."

            ti = t_min_i + h
            tj = t_min_j + w
            if (ti < N and tj < N):
                Tchar = T[ti][tj]
            else:
                Tchar = "."

            if Tchar != Schar:
                #print(False)
                return False
    return True

그리고는 4회 회전해 보십시오.

check.py

for _ in range(4):
    S = rotated(S)
    if make(S,T):
        print("Yes")
        exit()
print("No")