Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11BC3 - Color Ball

Từ đề thi tin học trẻ toàn quốc bảng C, 2012:

"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 × 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."

 

Bi đổi màu

+Gọi Sum(x,y,i,j) với 1<=i,x<=m-p+1 và 1<=j,y<=n-p+1 số bi xanh có được trên ma trận sau khi chọn hình vuông pxp có góc trên trái là (x,y) và đối phương chọn hình vuông pxp 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<=i<=m-p+1 và 1<=j<=n-p+1.

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

Input

Dòng đầu tiên chứa số m,n,p (1<=m,n<=100, 1<=p<=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).

Example

Input:

6 8 5
00022112
20221022
01102101
01021122
02211112
21000001

Output:
12 13 12 16
14 15 14 16

 

33.33% số test với m,n <= 10.

33.33% số test tiếp theo với m,n<=50.

33.33% số test tiếp theo với m,n <= 100.


Được gửi lên bởi:Duy Khanh Nguyen
Ngày:2012-08-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP PAS-GPC PAS-FPC
Nguồn bài:lấy ý tưởng từ bảng C tin học trẻ toàn quốc năm 2012. (khaihanhdk)

hide comments
2016-09-27 03:30:27
Code:
http://shink.in/J97Eg
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.