Nghệ thuật hiện đại (Platinum)

Điểm: 1,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

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

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

Trên canvas $N \times N$ ô vuông, người họa sĩ vẽ lần lượt $N^{2}$ hình chữ nhật theo thứ tự từ 1 đến $N^{2}$ , mỗi hình một màu riêng. Hình vẽ sau sẽ đè lên hình vẽ trước (che khuất một phần hoặc toàn bộ). Ô trống (chưa được tô) có giá trị 0.

Cho trạng thái canvas sau khi tất cả các hình đã được vẽ, hãy đếm xem có bao nhiêu màu có thể đã được vẽ đầu tiên (tức là màu đó hợp lệ với một thứ tự vẽ nào đó).

Gợi ý: Một màu $R$ không thể vẽ đầu tiên nếu tồn tại màu $S$ khác sao cho hình chữ nhật nhỏ nhất bao quanh các ô màu $S$ chứa ít nhất một ô màu $R$ — điều này có nghĩa $S$ phải được vẽ trước $R$ . Các màu không xuất hiện trên canvas (bị che hoàn toàn) đều có thể vẽ đầu tiên.

Dữ liệu vào

Dòng đầu: số nguyên $N$ .
$N$ dòng tiếp theo, mỗi dòng gồm $N$ số nguyên cách nhau bởi dấu cách, thể hiện màu của từng ô (0 nếu trống, nguyên dương nếu có màu).

Dữ liệu ra

Một số nguyên duy nhất — số lượng màu có thể được vẽ đầu tiên.

Ràng buộc

$1 \leq N \leq 1000$
Giá trị các ô trong $[0, N^{2}]$

Ví dụ

Input	Output	Giải thích
4 2 2 3 0 2 7 3 7 2 7 7 7 0 0 0 0	14	Màu 2 có thể vẽ đầu tiên. Màu 3 và 7 phải vẽ sau 2. Còn 13 màu không xuất hiện (1, 4–6, 8–16) đều có thể vẽ đầu tiên. Tổng cộng 14.
4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0	15	Màu 1 có thể vẽ đầu tiên. 15 màu còn lại không xuất hiện cũng đều có thể vẽ đầu tiên. Tổng 16. Nhưng vì chỉ có 1 màu hiện, tất cả $N^{2} - 1 = 15$ màu vô hình cộng với màu 1 = 16. Đáp án 15.
5 0 0 0 0 0 0 1 0 2 0 0 1 0 2 0 0 1 0 2 0 0 0 0 0 0	25	Màu 1 và 2 đều có thể vẽ đầu tiên (hình chữ nhật của chúng không chứa ô màu của nhau). 23 màu không hiện cũng hợp lệ. Tổng 25.

Bình luận

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