현대 좌석관리

import sys

maxy, maxx, order = map(int, input().split())
table = [[0]*(maxx+2) for i in range(maxy+2)] #앉는데
ID = [0]*(10**4+1) # 0은 안먹음, (x,y)은 먹는중 좌표, 1는 먹고감
#print(eat)

def nearest(x,y):
    minD = 1000
    for i in range(1, maxy+1):
        for j in range(1, maxx+1):
            #이미 자리가 앉아있는, 자리가 찬 좌석 중 가장 가까운 곳을 찾는다. 이것이 안전도가 될 것.
            if table[i][j] == 1 :
                d = (x-i)*(x-i) + (y-j)*(y-j)
                if d < minD :
                    minD = d
    return minD

def assign(num):
    maxD = 0
    for i in range(1, maxy+1):
        for j in range(1, maxx+1): 
            #맨 위부터 시작, 상하좌우가 다 비어있으면 이는 들어갈 수 있는 곳.
            if table[i][j] == 0 and table[i-1][j] == 0 and table[i+1][j] == 0 \
            and table[i][j-1] == 0 and table[i][j+1] == 0:
                #(i, j) 기준으로 거리를 잰다. 들어갈 수 있는 좌석의 찬 좌석과의 안전도를 구해, 최소 안전도 구함.
                # 이 최소 안전도가 가장 큰 자리가 (i,j)가 될 것이며, 여기에 앉게 됨.
                d = nearest(i,j)
                if d > maxD:
                    maxD = d
                    ID[num] = [i,j]

    #앉을 데가 없다면 false 반환
    #앉을 데가 있다면 table에 앉았음을 저장
    if maxD == 0:
        return False
    else :
        table[ID[num][0]][ID[num][1]] = 1
        return  True

for i in range(order):
    how, num = input().split()
    num = int(num)
    state = ID[num]
    
    if how == 'Out':
        if state == 0: #out인데 안 먹은 경우
            print(f'{num} didn\'t eat lunch.')
        elif state == 1: #out인데 이미 떠난 경우
            print(f'{num} already left seat.')
        else : #out인데 먹고 있는 경우
            print(f'{num} leaves from the seat({ID[num][0]}, {ID[num][1]}).')
            table[ID[num][0]][ID[num][1]] = 0
            ID[num] = 1
            
    else:
        if state == 0 : #in인데 안 먹은 경우
            if assign(num):
                print(f'{num} gets the seat ({ID[num][0]}, {ID[num][1]}).')
            else: #들어갈 자리가 없다면
                print('There are no more seats.')
        elif state == 1: #in인데 먹은경우
            print(f'{num} already ate lunch.')
        else: #in인데 이미 먹고있는 경우
            print(f'{num} already seated.')