NKDEC - Trang trí dàn đèn
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Nhân dịp Giáng sinh và năm mới, một cửa hàng lắp đặt một dàn đèn có dạng bảng hình chữ nhật m x n. Trên dàn đèn có một số vị trí cần lắp đặt bóng đèn. Cửa hàng muốn trang trí dàn đèn bằng các bóng đèn màu. Để thật đẹp mắt, cửa hàng muốn các bóng đèn nằm trên cùng hàng hoặc cùng cột đều khác màu nhau! Nhưng để đảm bảo sự hài hòa, dàn đèn không nên có quá nhiều màu.
Bạn hãy giúp cửa hàng trang trí dàn đèn, sao cho số loại bóng đèn màu cần sử dụng là ít nhất!
Dữ liệu
- Dòng đầu tiên chứa 2 số nguyên m, n (1 ≤ m, n ≤ 100)
- m dòng tiếp theo, mỗi dòng chứa n kí tự '0' hoặc '1' thể hiện dàn đèn, kí tự '1' cho biết vị trí cần lắp đặt bóng đèn.
Kết qủa
- Dòng đầu tiên: chứa số nguyên p là số loại bóng đèn màu ít nhất cần sử dụng.
- Dòng thứ i trong số m dòng tiếp theo chứa n số nguyên, số thứ j là chỉ số màu của bóng đèn ở vị trí tương ứng, hoặc là 0 nếu ở vị trí tương ứng không cần lắp đặt bóng đèn. Các màu được đánh số từ 1 đến p.
Ví dụ
Dữ liệu: 5 10 1100111010 0011000101 0001011000 0110001010 1111010100 Kết qủa 6 3 2 0 0 4 5 6 0 1 0 0 0 2 3 0 0 0 4 0 1 0 0 0 2 0 3 1 0 0 0 0 3 1 0 0 0 4 0 2 0 2 4 3 5 0 6 0 1 0 0
- Người up: paulmcvn