1. Tóm tắt đề bài

Cho một bảng số kích thước ~N \times M~. Hãy xoay bảng theo chiều kim đồng hồ ~90^\circ~ và in ra bảng kết quả (kích thước sau khi xoay là ~M \times N~).

• Dữ liệu vào (Input):
  • Dòng 1: Hai số nguyên ~N, M~ (~1 \le N, M \le 500~).
  • ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên.
• Dữ liệu ra (Output):
  • Gồm ~M~ dòng, mỗi dòng chứa ~N~ số nguyên sau khi xoay ~90^\circ~ theo chiều kim đồng hồ.

2. Phân tích bài toán & Giới hạn

• Giới hạn kích thước: ~N, M \le 500~.

  • Số lượng phần tử tối đa trong ma trận là ~500 \times 500 = 250\,000~.
  • Quy mô này rất nhỏ, thuật toán đọc và in kết quả chỉ tốn vài chục mili-giây (~< 0.05~ giây), không lo bị quá thời gian.

• Quy luật biến đổi tọa độ khi xoay ~90^\circ~ theo chiều kim đồng hồ:

  • Giả sử ma trận ban đầu là ~A~ kích thước ~N \times M~ (với các chỉ số dòng ~i \in [1, N]~, cột ~j \in [1, M]~).
  • Khi xoay ~90^\circ~ theo chiều kim đồng hồ:
    • Cột thứ ~j~ của ma trận ban đầu sẽ biến thành dòng thứ ~j~ của ma trận mới.
    • Thứ tự các phần tử trên cột thứ ~j~ sẽ đi từ dưới lên trên (từ hàng ~N~ về hàng ~1~).
  • Như vậy, phần tử ở hàng mới ~r~ (~1 \le r \le M~) và cột mới ~c~ (~1 \le c \le N~) chính là phần tử ban đầu: ~B_{r, c} = A_{N - c + 1, r}~

3. Thuật toán xử lý

• Ý tưởng:

  1. Đọc hai số ~N, M~ và lưu toàn bộ ma trận ~A~ kích thước ~N \times M~.
  2. Để in ra ma trận sau khi xoay kích thước ~M \times N~, ta duyệt trực tiếp thứ tự in mà không cần tạo thêm mảng phụ:
     • Dòng mới chạy từ ~j = 1~ đến ~M~:
       • Cột mới chạy từ ~i = N~ lùi về ~1~:
         • In ra phần tử ~A[i][j]~ kèm theo dấu cách.
       • Xuống dòng sau mỗi hàng được in xong.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(N \times M)~ — Thao tác duyệt và in mỗi phần tử đúng 1 lần, thực thi tức thời.
  • Không gian (bộ nhớ): ~\mathcal{O}(N \times M)~ — Lưu ma trận ~500 \times 500~ chỉ tiêu tốn khoảng ~1\text{ MB}~, hoàn toàn tối ưu bộ nhớ.