""" # 벽 -> 참가자 이동X 회전할때 내구도 깎임 0: 빈칸
# 출구 도착시 탈출
# 참가자 이동 로직
# 움직일 수 있는 칸 2칸이상 -> 상하로 움직임
# 출구까지 최단거리
# 한칸에 참가자 두명 가능
# 미로 회전 로직
def move_man():
queue = deque([])
# 출구와 가까운 곳으로 이동 ex,ey : 출구 좌표
direct = ((1,0),(-1,0),(0,1),(0,-1))
MIN = float('inf')
for i in range(4)
x = qx + direct[i][0]
y = qy + direct[i][1]
dist = abs(x - ex) + abs(y - ey)
if dist < MIN:
# 해당 참가자는 작은 좌표로 이동
def squere():# 출구와 한명이상의 참가자가 있는 정사각형 구하는 로직
ex, ey # 출구 좌표
# 사람 좌표
#
for i in range(N):
for j in range(N):
if maps[i][j] == 사람이면:
return
def rotate_map():
# 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형
sr,sc,size = squere() # 정사각형 시작좌표와 크기
# 시계방향 회전
for i in range(sr,sr + size):
for j in range(sc,sc+size):
maps[j][size-1+i] = maps[i][j]
if maps[j][size-1+i]>0:
maps[j][size-1+i] -= 1 # 내부에 있는 벽 내구도 깎기
while K>0:
move_man()
rotate_map()
if man == 다 탈출:
break
K -= 1
"""
from collections import deque
N,M,K = map(int,input().split())
maps = [list(map(int,input().split())) for _ in range(N)]
man_point = [list(map(int,input().split())) for _ in range(M)]
ex, ey = map(int,input().split()) # 출구 좌표
ex, ey = ex - 1, ey - 1
move = 0
# 미로 회전 로직
def move_man(man):
global move, maps
queue = deque(man)
# 출구와 가까운 곳으로 이동 ex,ey : 출구 좌표
direct = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
# 각 참가자들은 1초에 한칸씩 움직이는거
while queue:
q = queue.popleft()
MIN = float('inf')
qx, qy = q[0],q[1]
MIN_point = [qx,qy]
for i in range(4):
x = qx + direct[i][0]
y = qy + direct[i][1]
if x == ex and y == ey:
MIN_point = [x, y]
# 참가자 탈출하면 next는 없음
break
# 출구와 가까워지는 방향에 대해 멀어지면 이동 X
if 0 <= x < N and 0 <= y < N and maps[x][y] <= 0:
move_dist = abs(x - ex) + abs(y - ey)
origin_dist = abs(qx - ex) + abs(qy - ey) # 이동 전 거리
if move_dist < origin_dist: # 이동한 거리가 이동 전 거리보다 출구에 가깝다면
if move_dist < MIN:
MIN = move_dist
MIN_point = [x,y]
nx, ny = MIN_point[0], MIN_point[1]
if maps[nx][ny] != 10 and [nx,ny] != [qx,qy]:
cnt = maps[qx][qy]
maps[nx][ny] = maps[nx][ny] + cnt
maps[qx][qy] = 0
move += cnt
elif maps[nx][ny] == 10:
cnt = maps[qx][qy]
move += cnt
maps[qx][qy] = 0
return
def square(): # 출구와 한명이상의 참가자가 있는 정사각형 구하는 로직
MIN_size = float('inf')
MIN_point = []
for i in range(len(man_point)):
x,y = man_point[i][0] ,man_point[i][1] # 사람 좌표
# 가로, 세로 길이 중 긴것이 정사각형 한 변의 길이가됨
size = max(abs(x-ex),abs(y-ey)) + 1
if MIN_size > size:
MIN_point = [x,y]
MIN_size = size
elif MIN_size == size and MIN_point[0] > x:
MIN_point = [x,y]
elif MIN_size == size and MIN_point[0] == x and MIN_point[1] > y:
MIN_point = [x,y]
# 먼저 직사각형 영역만큼 확인
min_x = min(MIN_point[0], ex)
min_y = min(MIN_point[1], ey)
max_x = max(MIN_point[0], ex)
max_y = max(MIN_point[1], ey)
start_x, start_y, end_x, end_y = min_x, min_y, max_x, max_y
if abs(min_y - max_y) == abs(min_x - max_x):
start_x,start_y = min_x,min_y
end_x,end_y = max_x,max_y
# 직사각형 영역에서 짧은 영역을 위나 아래로 size 길이가 되게 만들어야함
elif abs(min_y - max_y) > abs(min_x - max_x): # y보다 작은 x 값을 늘려준다
extend_size = MIN_size - (abs(min_x - max_x) + 1)
start_x = min_x - extend_size # 우선 왼쪽으로 확장해본다
end_x = max_x
if start_x < 0: # 위쪽으로 못밀면 못 민만큼 아래쪽으로 확장
end_x = min(N-1,max_x + abs(start_x))
start_x = 0
elif abs(min_y - max_y) < abs(min_x - max_x): # x보다 작은 y값을 늘려준다
extend_size = MIN_size - (abs(min_y - max_y) + 1)
start_y = min_y - extend_size
end_y = max_y
if start_y < 0: # 왼쪽으로 못밀면 못 민만큼 오른쪽으로 확장
end_y = min(N - 1, max_y + abs(start_y))
start_y = 0
return start_x,start_y,end_x,end_y
def rotate_map():
global maps, ex, ey, man_point
# 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형
sr, sc, er, ec = square() # 정사각형 시작 좌표와 끝 좌표
size = er - sr + 1 # 정사각형의 크기는 sr, er 사이의 차이 + 1
new_maps = [[0]*size for i in range(size)] # 회전된 결과를 저장할 새로운 배열
# 시계 방향으로 회전
for i in range(size):
for j in range(size):
new_maps[j][size - 1 - i] = maps[sr + i][sc + j] # 좌표 변환하여 회전
if 0 < new_maps[j][size - 1 - i] < 10:
new_maps[j][size - 1 - i] -= 1 # 내부에 있는 벽 내구도 깎기
# 근데 사람도 같이 회전해야함
# 회전한 결과를 원래 배열에 반영
for i in range(size):
for j in range(size):
maps[sr+i][sc+j] = new_maps[i][j]
# 출구 좌표 갱신 (-1이 출구라면)
if maps[sr+i][sc+j] == 10:
ex, ey = sr+i, sc+j
# print(f'size: {size}, r:{sr},c:{sc}')
# print(f'exit: {ex},{ey}')
for i in range(len(man_point)):
man_point[i][0] -= 1
man_point[i][1] -= 1
x = man_point[i][0]
y = man_point[i][1]
maps[x][y] -= 1
maps[ex][ey] = 10
while K>0:
move_man(man_point)
man_point = []
for i in range(N):
for j in range(N):
if maps[i][j] < 0:
man_point.append([i,j])
if man_point == []:
break
rotate_map()
man_point = []
for i in range(N):
for j in range(N):
if maps[i][j] < 0:
man_point.append([i,j])
if man_point == []: # 다 탈출하면
break
K -= 1
# 모든 참가자들의 이동 거리 합과 출구 좌표 출력
print(-1*move)
print(ex+1,ey+1)
정사각형을 완전탐색으로 찾아서 구현
자자 완창한다.
동시에 움직이는 상황이면 뭐다? 복사 or 0으로 새로운 배열 만들기
무조건 배열을 복사하거나 새로 만들어서 최종적으로 움직인 다음
전역변수에 다시 넣어준다.
한번 더 완창한다.
회전하는 상황이면 뭐다?복사 or 0으로 새로운 배열 만들기
90도 회전하는 코드는 뭐다?
new_maps = [x[:] for x in maps] # maps는 원본 이라 하고 복사하기
for i in range(N):
for j in range(N):
new_maps[i][j] = maps[N-1-j][i]
maps = new_maps
머리 팍! 치면 코드 팍! 나와야한다.
from collections import deque
N,M,K = map(int,input().split())
maps = [list(map(int,input().split())) for _ in range(N)]
man_point = [list(map(int,input().split())) for _ in range(M)]
ex, ey = map(int,input().split()) # 출구 좌표
ex, ey = ex - 1, ey - 1
remain_man = M # 모든 참가자가 나갔는지 확인하기 위함
def move():
global move_cnt, remain_man, maps
# 출구와 가까워지는 방향으로
# 머물러 있던 칸 보다 출구까지의 최단거리가 가까워야함
direction = ((1,0),(-1,0),(0,1),(0,-1))
new_maps = [x[:] for x in maps]
for i in range(N):
for j in range(N):
if -11 < maps[i][j] < 0: # 사람이면 이동해야지..
for d in range(4):
x = i + direction[d][0]
y = j + direction[d][1]
# 움직인 칸은 현재 칸 보다 가까워야한다.
if abs(ex - i) + abs(ey - j) > abs(ex - x) + abs(ey - y):
if 0 <= x < N and 0 <= y < N and maps[x][y] <= 0:
"""음수 주의"""
new_maps[i][j] -= maps[i][j] # 이동처리 (움직이기 전 자리는 나간만큼 채워준다)
move_cnt += maps[i][j]
if x == ex and y == ey: # 만약 이동한 곳이 출구라면
remain_man += maps[i][j] # 나간만큼 빼준다
# 좌표 갱신 없음. 나가서
else:
new_maps[x][y] += maps[i][j] # 이동처리 (새로운 좌표 갱신)
break
maps = new_maps # 복사
def find_square():
# 가장 작은 사각형 찾기
MIN = N-1
for i in range(N):
for j in range(N):
if -11 < maps[i][j] < 0:
MIN = min(MIN,max(abs(ex - i)+1,abs(ey - j)+1))
# MIN size 의 정사각형 찾기
start_x = N-1
start_y = N-1
man_list = []
for i in range(N):
for j in range(N):
if -11 < maps[i][j] < 0:
man_list.append([i,j])
for sr in range(N-MIN+1):
for sc in range(N-MIN+1):
if (sr <= ex < sr + MIN and sc <= ey < sc + MIN):
for x,y in man_list:
if (sr <= x < sr + MIN) and (sc <= y < sc + MIN):
start_x = sr
start_y = sc
return start_x, start_y, MIN
return start_x,start_y,MIN
def rotate(sr,sc,size):
global maps, ex,ey
new_maps = [[0]*size for _ in range(size)] # 맵 복사
for i in range(size):
for j in range(size):
new_maps[i][j] = maps[sr+size-1-j][sc+i]
if new_maps[i][j] > 0:
new_maps[i][j] -= 1
for i in range(size):
for j in range(size):
maps[sr+i][sc+j] = new_maps[i][j]
if maps[sr+i][sc+j] == -11:
ex,ey = sr+i,sc+j
for k in range(M):
x,y = man_point[k]
maps[x-1][y-1] -= 1 # 참가자들 표시
maps[ex][ey] = -11 # 출구같은게 있으면 조건절 범위 확인 후 적용!
move_cnt = 0 # 모든 참가자들의 이동 거리함
while K > 0 and remain_man > 0 :
move()
if remain_man == 0:
break
# print('move',move_cnt)
# for i in maps:
# print(i)
sr,sc,size = find_square()
# print(sr,sc,size)
# for i in maps:
# print(i)
rotate(sr,sc, size)
K -= 1
print(-move_cnt)
print(ex+1,ey+1)
