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

Cho ma trận ảnh số ~A~ cấp ~N \times M~. Hãy tính ma trận kết quả ~B~ cấp ~(N - 2) \times (M - 2)~, trong đó mỗi phần tử ~B_{i, j}~ bằng tổng của khối ~3 \times 3~ có góc trên trái tại ô ~(i, j)~ trong ma trận ~A~:

~ B_{i, j} = \sum_{u=0}^{2} \sum_{v=0}^{2} A_{i+u, j+v} ~

• Dữ liệu vào (Input):
  • Dòng 1: Hai số nguyên ~N, M~ (~3 \le N, M \le 1000~).
  • ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số nguyên.
• Dữ liệu ra (Output):
  • Ghi ra ~N - 2~ dòng, mỗi dòng gồm ~M - 2~ số nguyên của ma trận ~B~.

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

• Giới hạn kích thước: ~N, M \le 1000~.
  • Kích thước ma trận ~B~ tối đa là ~(1000 - 2) \times (1000 - 2) \approx 10^6~ phần tử.
• Đánh giá thuật toán duyệt trực tiếp:
  • Với mỗi ô ~(i, j)~ của ma trận ~B~, việc tính tổng một khối cố định ~3 \times 3~ chỉ tốn đúng ~9~ phép cộng.
  • Tổng số thao tác trên toàn bộ ma trận: ~\approx 9 \times (N - 2) \times (M - 2) \le 9 \times 10^6~ phép tính.
  • Ngưỡng ~9 \times 10^6~ hoàn toàn chạy tốt trong thời gian cho phép (~< 0.2~ giây trên DMOJ).

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. Sử dụng hai vòng lặp lồng nhau để duyệt vị trí góc trên trái ~(i, j)~ của từng khối ~3 \times 3~:
     • Biến ~i~ chạy từ ~1~ đến ~N - 2~ (chỉ số dòng).
     • Biến ~j~ chạy từ ~1~ đến ~M - 2~ (chỉ số cột).
  3. Tại mỗi vị trí ~(i, j)~, tính tổng 9 ô: ~sum = \sum_{u=0}^{2} \sum_{v=0}^{2} A[i + u][j + v]~
  4. In giá trị ~sum~ kèm theo dấu cách; sau khi kết thúc một dòng (hết biến ~j~), thực hiện xuống dòng.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(N \times M)~ — Với mỗi ô chỉ thực hiện ~9~ phép cộng hằng số, tổng thời gian ~\le 0.15~ giây.
  • Không gian (bộ nhớ): ~\mathcal{O}(N \times M)~ — Lưu trữ mảng kích thước ~1000 \times 1000~ chỉ tốn khoảng ~4\text{ MB}~, hoàn toàn tối ưu.