Sereja và Bảng

Điểm: 8,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một bảng nhị phân kích thước $n \times m$ , mỗi ô chứa một giá trị $0$ hoặc $1$ . Bảng được gọi là tốt nếu mọi thành phần liên thông gồm các ô cùng giá trị đều tạo thành một hình chữ nhật đặc (các cạnh song song với cạnh bảng và mọi ô bên trong đều thuộc thành phần).

Hai ô được coi là kề nhau nếu chúng nằm cạnh nhau trong cùng một hàng hoặc cùng một cột.

Bạn được phép thay đổi giá trị của không quá $k$ ô (đổi $0$ thành $1$ hoặc ngược lại). Hãy xác định số ô tối thiểu cần thay đổi để bảng trở thành bảng tốt, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$ , $m$ , $k$ .
$n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên $a_{i, j} \in {0, 1}$ mô tả bảng.

Dữ liệu ra

In ra một số nguyên — số ô tối thiểu phải thay đổi để bảng trở thành bảng tốt, hoặc $- 1$ nếu không thể thực hiện được với không quá $k$ thay đổi.

Ràng buộc

$1 \leq n, m \leq 100$
$1 \leq k \leq 10$
$a_{i, j} \in {0, 1}$

Ví dụ

Input	Output	Giải thích
3 4 1 1 0 0 1 0 1 1 0 1 0 0 1	0	Bảng đã là bảng tốt: các hàng xen kẽ giữa hai mẫu bù nhau, mỗi thành phần liên thông là một ô riêng lẻ (hình chữ nhật $1 \times 1$ ).
5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1	1	Đổi ô $(3, 3)$ từ $0$ thành $1$ cho ra bảng toàn $1$ — hợp lệ.
3 4 1 1 0 0 0 0 1 1 1 1 1 1 0	-1	Không tồn tại cách đổi không quá $1$ ô để bảng trở nên tốt.

Bình luận

Không có bình luận tại thời điểm này.