Color Ball

View as PDF

Submit solution

Points: 1.48 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
lấy ý tưởng từ bảng C tin học trẻ toàn quốc nãm 2012. (khaihanhdk)
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Trò chơi "Bi đổi mầu" là trò chơi đối kháng gồm hai người chơi trên lưới hình chữ nhật mxn ô vuông. Các dòng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái qua phải. Ô nằm ở vị trí dòng ~i~ và cột ~j~ của lưới được gọi là ô ~(i~, ~j)~ và khi đó, ~i~ được gọi là toạ độ dòng còn ~j~ được gọi là toạ độ cột của ô này.

Tại mỗi lượt chơi, mỗi người trong hai người chọn một hình vuông kích thước ~p \times p~ của mình rồi bí mật viết ra một mảnh giấy hai số là tọa độ góc trái trên của hình vuông mà mình chọn. Sau đó cả hai công bố hình vuông của mình. Những viên bi nằm trong hình vuông mà hai người chơi chọn sẽ bị đổi màu, trừ những viên bi nằm trong cả hai hình vuông. Xét trường hợp bi của bạn là màu xanh.

  • Gọi ~Sum(x, y, i, j)~ với ~1 \le i, x \le m-p + 1~ và ~1 \le j, y \le n-p + 1~ số bi xanh có được trên ma trận sau khi chọn hình vuông ~p \times p~ có góc trên trái là ~(x~, ~y)~ và đối phương chọn hình vuông ~p \times p~ có góc trên trái là ~(i~, ~j)~.
  • Gọi ~Msum(x, y)~ là ~min(sum(x, y, i, j))~ với mọi ~1 \le i \le m-p + 1~ và ~1 \le j \le n-p+ 1~.

Yêu cầu: Tính tất cả ~Msum(x, y)~ với mọi ~1 \le x \le m-p+1~ và ~1 \le y \le n-p + 1~.

Input

Dòng đầu tiên chứa số ~m~, ~n~, ~p~ ~(1 \le m~, ~n \le 100~, ~1 \le p \le~ ~min(m~, ~n))~.

~m~ dòng sau: mỗi dòng chứ kí tự '0' hoặc '1' hoặc '2' -- '0' tương ứng với ô không có bi, '1' tương ứng với ô có bi xanh, '2' tương ứng với ô có bi đỏ.

Output

Gồm ~m-p + 1~ dòng, mỗi dòng ~i~ chứa ~n-p+ 1~ số nguyên là ~Msum(i, 1)~, ~Msum(i, 2)~, ..., ~Msum(i, n-p+ 1)~.

Giới hạn

  • ~33.33\%~ số test với ~m, n \le 10~.
  • ~33.33\%~ số test tiếp theo với ~m, n \le 50~.
  • ~33.33\%~ số test tiếp theo với ~m, n \le 100~.

Sample Input

6 8 5
00022112
20221022
01102101
01021122
02211112
21000001

Sample Output

12 13 12 16
14 15 14 16

Comments

Please read the guidelines before commenting.


There are no comments at the moment.