[BOJ 16927]回転配列2
12131 ワード
BOJ 16926配列回転1では、回転数Rが最大10910^9109に増加する.一番外側のケースは丸いキューになっています.このときQの大きさをQと呼びましょう の回転数はRではなくQmod RQmod RQmodなので変換効率が高い. は、再びクラブの前部からハウジングを充填する. の内側のハウジングが存在しなくなるまで繰り返します. したがって、回転シェルの関数を定義します.
また、内層に入るには、マトリクスの左上隅の座標値を1ずつ増加させ、右下隅の座標値を1ずつ減少させることができる.
rotate_part(A, x1, y1, x2, y2, R)
:A
:NxM
行列(x1, y1)
:行列の左上隅(x2, y2)
:行列の右下隅R
:回転数また、内層に入るには、マトリクスの左上隅の座標値を1ずつ増加させ、右下隅の座標値を1ずつ減少させることができる.
import sys
#sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline
from collections import deque
def print_matrix(A, N, M):
for i in range(N):
for j in range(M):
print(A[i][j], end=' ')
print()
print()
def rotate_part(A, x1, y1, x2, y2, R):
q = deque()
for j in range(y1, y2):
q.append(A[x1][j])
for i in range(x1, x2):
q.append(A[i][y2])
for j in range(y2, y1, -1):
q.append(A[x2][j])
for i in range(x2, x1, -1):
q.append(A[i][y1])
Q = len(q)
for _ in range(R % Q):
element = q.popleft()
q.append(element)
for j in range(y1, y2):
A[x1][j] = q.popleft()
for i in range(x1, x2):
A[i][y2] = q.popleft()
for j in range(y2, y1, -1):
A[x2][j] = q.popleft()
for i in range(x2, x1, -1):
A[i][y1] = q.popleft()
N, M, R = map(int, input().split())
A = []
for _ in range(N):
A.append(list(map(int, input().split())))
for i in range(min(N, M) // 2):
rotate_part(A, i, i, N - 1 - i, M - 1 - i, R)
print_matrix(A, N, M)
Reference
この問題について([BOJ 16927]回転配列2), 我々は、より多くの情報をここで見つけました https://velog.io/@ahj1592/BOJ-16927-배열-돌리기-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol