Thung Lũng

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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

Cho lưới $N \times N$ với độ cao $h_{i, j}$ tại ô $(i, j)$ , tất cả đôi một phân biệt.

Một thung lũng là một tập hợp $V$ các ô thỏa mãn:

$V$ liên thông theo cạnh (các ô trong $V$ kết nối được qua di chuyển lên/xuống/trái/phải)
Mọi ô kề cạnh $V$ nhưng không thuộc $V$ đều có độ cao cao hơn mọi ô trong $V$
$V$ không có "lỗ hổng" (bù của $V$ liên thông theo đường chéo + vô cực)

Tính tổng kích thước của tất cả các thung lũng.

Dòng đầu: số nguyên $N$ ( $1 \leq N \leq 750$ )
$N$ dòng tiếp theo, mỗi dòng $N$ số nguyên: độ cao $h_{i, j}$ ( $1 \leq h_{i, j} \leq 10^{6}$ , đôi một phân biệt)

Tổng kích thước tất cả các thung lũng.

Input	Output	Giải thích
3 1 10 2 20 100 30 3 11 50	30	Các thung lũng hợp lệ: {(0,0)} kích thước 1; {(0,2)} kích thước 1; {(2,0)} kích thước 1; {(0,0),(0,1),(0,2)} kích thước 3; {(2,0),(2,1)} kích thước 2; {(0,0),(0,1),(0,2),(1,0),(2,0),(2,1)} kích thước 6; {(0,0),...,(1,2)} kích thước 7; {toàn bộ lưới} kích thước 9. Tổng = 1+1+1+3+2+6+7+9 = 30.

Bình luận

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