Xoay từng vành của ma trận

Bối cảnh

Một ảnh số được lưu trong ma trận. Bộ xử lý không xoay toàn bộ ảnh như phép quay 90 độ thông thường mà thực hiện một phép biến đổi đặc biệt: mỗi vành đồng tâm được xoay theo chiều kim đồng hồ k bước, độc lập với các vành khác.

Vành 0 là biên ngoài. Vành 1 là biên của phần còn lại sau khi bỏ vành 0, và tiếp tục cho tới khi không còn khung có ít nhất 2 hàng và 2 cột. Nếu còn một hàng hoặc một cột nằm ở chính giữa, các ô đó không thuộc vành nào và giữ nguyên.

Để xoay một vành, hãy đọc các ô theo thứ tự chiều kim đồng hồ bắt đầu từ góc trái trên của vành. Sau phép xoay phải k bước trên chuỗi này, ghi các giá trị trở lại đúng các tọa độ theo cùng thứ tự.

Bài Hard yêu cầu kết hợp traversal theo lớp, ánh xạ ma trận ↔ dãy 1 chiều và phép xoay vòng. Không dùng vector, STL hoặc con trỏ.

Khó nhất là xây dựng thứ tự tọa độ nhất quán để lúc đọc và lúc ghi không lệch, đồng thời không lấy trùng bốn góc.

Yêu cầu

1. Với mỗi layer, xác định top/left/bottom/right.
2. Trích chuỗi theo: cạnh trên, cạnh phải bỏ góc trên, cạnh dưới đi ngược bỏ góc phải, cạnh trái đi lên bỏ hai góc.
3. Xoay phải chuỗi shift=k%len bằng mảng phụ.
4. Ghi ngược lại theo chính thứ tự tọa độ đã dùng.
5. Các ô không thuộc layer được giữ nguyên.

Input

Dòng 1: rows cols k; sau đó ma trận.

Output

In ma trận sau khi mỗi vành được xoay theo chiều kim đồng hồ k bước.

Ràng buộc

1 ≤ rows,cols ≤ 100, 0 ≤ k ≤ 10^18, |a[i][j]| ≤ 10^9.

Ví dụ 1

Input

4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Output

5 1 2 3
9 10 6 4
13 11 7 8
14 15 16 12

Giải thích

Ma trận 4×4 có hai vành. Với vành ngoài, dãy phần tử khi đi theo chu vi theo chiều kim đồng hồ từ góc trái trên là 1,2,3,4,8,12,16,15,14,13,9,5; xoay k=1 làm mỗi phần tử tiến một vị trí, nên 5 chuyển lên (0,0), 1 sang (0,1), ... 9 xuống (1,0). Vành trong 2×2 có chuỗi 6,7,11,10 và cũng xoay một bước thành 10,6,7,11 trên chu vi tương ứng. Ghép hai vành lại tạo đúng ma trận output 5 1 2 3 / 9 10 6 4 / 13 11 7 8 / 14 15 16 12.

Ví dụ 2

Input

3 5 2
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

Output

11 6 1 2 3
12 7 8 9 4
13 14 15 10 5

Giải thích

Ma trận 3×5 chỉ có một vành hoàn chỉnh vì min(3,5)/2 = 1; ba ô giữa của hàng 1 (7 8 9) không thuộc vành và giữ nguyên. Chuỗi chu vi được xoay tiến k=2 vị trí theo chiều đi quanh vành, nên hai phần tử cuối của chuỗi cũ 11,6 xuất hiện ở đầu chuỗi mới tại (0,0),(0,1). Phân phối tiếp các phần tử quanh chu vi cho ta hàng đầu 11 6 1 2 3, hai biên bên 12...4 và 13...5, còn hàng cuối 13 14 15 10 5. Vì vậy ma trận output khớp chính xác phép xoay 2 bước.

Thông tin học tập

• Module: M03
• Buổi: B12
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: 2D static arrays, concentric rings, coordinate extraction, cyclic rotation, matrix transformation
• Giới hạn kiến thức: B01-B12
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100