Tô Màu Theo Số

Đ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 một lưới $N \times M$ ô, mỗi ô được tô một trong 26 màu (chữ cái in hoa A–Z). Với mỗi truy vấn, bạn được cho một hình chữ nhật con của lưới, hãy đếm số vùng liên thông của các ô cùng màu trong hình chữ nhật đó.

Hai ô được coi là liền kề nếu chúng chia sẻ một cạnh chung. Một vùng liên thông là tập hợp tối đa các ô cùng màu mà có thể đi từ ô này sang ô kia chỉ qua các ô liền kề cùng màu.

Dữ liệu vào

Dòng đầu: ba số nguyên $N$ , $M$ , $Q$ .
$N$ dòng tiếp theo: mỗi dòng là một xâu $M$ ký tự in hoa (màu của các ô trong hàng đó).
$Q$ dòng tiếp theo: mỗi dòng chứa bốn số nguyên $x_{1}$ , $y_{1}$ , $x_{2}$ , $y_{2}$ — hình chữ nhật con từ hàng $x_{1}$ , cột $y_{1}$ đến hàng $x_{2}$ , cột $y_{2}$ (1-indexed, bao gồm cả hai đầu mút).

Dữ liệu ra

Với mỗi truy vấn, in ra số vùng liên thông trên một dòng riêng.

Ràng buộc

$1 \leq N, M \leq 1000$
$1 \leq Q \leq 1000$
$1 \leq x_{1} \leq x_{2} \leq N$ , $1 \leq y_{1} \leq y_{2} \leq M$

Ví dụ

Input	Output	Giải thích
4 8 9 ABBAAAAA ABAAAABA CAADABBA AAAAAAAA 1 1 4 8 3 5 3 8 1 3 2 4 1 4 2 5 1 1 3 3 4 4 4 4 2 6 4 8 3 5 4 6 1 6 3 8	6 3 2 1 4 1 3 2 2	Truy vấn đầu tiên (toàn bộ lưới): có 6 vùng liên thông — một vùng A lớn, hai vùng B riêng lẻ (góc trên trái và vùng B liền nhau), một vùng C, một vùng D, và một vùng B khác. Truy vấn thứ hai (hàng 3, cột 5–8): "ABBA" → 3 vùng: A, BB, A.

Ghi chú

Giới hạn bộ nhớ: 512MB. Giới hạn thời gian cao hơn 50% so với thông thường.

Bình luận

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