Rào cây kiểu Bờm

Nguồn: CLUE OJ – Chương 11: Mảng 2 chiều Độ khó: Dễ Mảng 2 chiều Duyệt 4 hướng

Đề bài

RAOCAY – Rào cây kiểu Bờm. Trên một mảnh vườn hình chữ nhật kích thước $M \times N$, Bờm gieo hạt trồng cây theo từng hàng và từng cột đều nhau. Tuy nhiên, do Bờm bảo quản hạt giống chưa tốt, nên không phải tất cả các hạt giống gieo xuống đều nảy mầm. Để bảo vệ các mầm cây mới mọc, Bờm quyết định rào chúng lại. Tuy nhiên, Bờm không rào xung quanh mảnh vườn như mọi người mà rào từng vùng có các cây liền kề cạnh với nhau.

Yêu cầu: hãy xác định độ dài hàng rào mà Bờm cần dựng, biết rằng các hạt giống được gieo cách đều nhau 1 đơn vị chiều dài theo hàng và cột.

Input:

• Dòng đầu ghi 2 số nguyên dương $M$ và $N$ $(2 \le M, N \le 1000)$.
• $M$ dòng tiếp theo, mỗi dòng ghi $N$ số 0 hoặc 1, tương ứng với tình trạng không hay có hạt nảy mầm.

Output: ghi số nguyên cho biết độ dài hàng rào cần dựng.

Lưu ý trên CLUE OJ: dữ liệu đọc từ bàn phím và in ra màn hình, đề bài có yêu cầu từ file thì cứ kệ nó.

Ví dụ – input

5 5
1 0 1 0 0
1 1 1 1 0
0 0 1 0 1
0 1 0 0 1
1 0 1 1 0

Ví dụ – output

36

Giải thích ví dụ (hình trong đề): các vùng cây liền kề được tô màu, đường viền của mỗi vùng chính là hàng rào. Có 5 vùng, tổng chiều dài hàng rào là $36$.

Lời mở đầu

Đọc đề thấy chữ "rào từng vùng" là nhiều bạn nghĩ ngay tới loang (BFS/DFS) để tìm từng vùng rồi tính chu vi từng vùng. Làm vậy được nhưng hơi dài dòng. Thật ra mình không cần biết vùng nào là vùng nào: chỉ cần nhìn từng cây và đếm xem nó cần bao nhiêu đoạn rào. Bài này là bài tập rất tốt để luyện kỹ thuật duyệt 4 ô kề bằng mảng hướng dx[], dy[] và mẹo thêm viền 0 quanh mảng để khỏi phải kiểm tra ra ngoài.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngCạnh nào cần ràoCách 1Duyệt 4 ô kềCách 24·cây − 2·cặp

Bộ testBộ test chính thức có gì?

Bộ test có 100 test. Đề không ghi subtask, nhưng nhìn vào bộ test thì thấy rõ 2 mức: 20 test đầu rất nhỏ ($M, N \le 10$, dùng để kiểm tra tính đúng), còn 80 test sau đều là vườn lớn nhất $1000 \times 1000$ với khoảng một nửa số ô có cây (đầu vào khoảng 2 MB).

Test	M	N	Số cây	Đáp án	Ghi chú
1 – 20	2 – 10	3 – 9	5 – 29	14 – 78	Nhỏ, kiểm tra tay được
21 – 100	1000	1000	499784 – 500213	1000770 – 1001192	Lớn nhất, khoảng một nửa số ô có cây

Mức	Điều kiện	Test	Cách đạt
Nhỏ	$M, N \le 10$	1 – 20	Cách 1, Cách 2
Lớn	$M = N = 1000$	21 – 100	Cách 1, Cách 2

Vì các vườn lớn sinh ngẫu nhiên nên đáp án đều quanh mức $10^6$, không vượt quá giới hạn kiểu int. Điều quan trọng với 80 test lớn là đọc dữ liệu nhanh và thuật toán $O(M \cdot N)$.

Ý tưởngMỗi cây có 4 cạnh – cạnh nào cần rào?

Hãy tưởng tượng mỗi cây chiếm một ô vuông $1 \times 1$. Ô đó có 4 cạnh: trên, dưới, trái, phải. Xét từng cạnh:

• Nếu bên kia cạnh là một cây khác thì 2 cây thuộc cùng một vùng, hàng rào không đi qua cạnh này.
• Nếu bên kia cạnh là đất trống (số 0) hoặc ngoài mảnh vườn thì cạnh này nằm trên đường viền của vùng, phải dựng 1 đơn vị rào.

Kết luận

Độ dài hàng rào = tổng, trên mọi cây, số cạnh của cây đó giáp với đất trống hoặc ngoài vườn.

Cách nghĩ này tự động đúng cho mọi hình dạng vùng, kể cả vùng có "lỗ" ở giữa (khi đó Bờm phải rào cả mép trong của lỗ, vì mầm cây giáp với đất trống ở đó). Mình đã kiểm tra công thức này khớp với đáp án của cả 100 test.

Em sửa mảnh vườn rồi bấm Tiếp để xem từng cây "góp" bao nhiêu đoạn rào. Đoạn cam là rào vừa thêm, đoạn nâu là rào đã dựng trước đó, nét đứt xanh là cạnh chung giữa 2 cây (không cần rào):

Mảnh vườn (mỗi hàng viết liền)

Ví dụ nhanh:

Cách 1Duyệt 4 ô kề của từng cây

Lưu cả mảnh vườn vào mảng a, đánh số từ 1. Mẹo quan trọng: hàng 0, hàng $M + 1$, cột 0, cột $N + 1$ của mảng luôn bằng 0 (mảng toàn cục tự khởi tạo 0), đóng vai trò "ngoài vườn". Nhờ vậy khi xét ô kề của cây nằm ở mép vườn, ta không cần kiểm tra chỉ số có ra ngoài hay không – ô kề đó cứ là 0, nghĩa là cần rào.

C++▶ Chạy tay từng dòng codeCách 1: mỗi cây xét 4 ô kề, ô kề bằng 0 (đất trống hoặc viền ngoài) thì cần 1 đoạn rào.

Dữ liệu vào (stdin) – sửa thoải mái5 5 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Hai mảng dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1} mô tả 4 hướng lên, xuống, trái, phải. Ô kề theo hướng k là (i + dx[k], j + dy[k]).
2. Mảng khai báo a[1005][1005] (lớn hơn $M + 2$) để chỗ cho viền 0, và phải khai báo toàn cục: mảng $10^6$ phần tử khai báo trong main vừa không tự bằng 0, vừa dễ tràn bộ nhớ ngăn xếp.
3. Đáp án tối đa $4 \cdot 10^6$ (vườn $1000 \times 1000$ kiểu bàn cờ), vẫn vừa int; mình dùng long long cho chắc tay.
4. Input có tới $10^6$ số nên nhớ ios::sync_with_stdio(0); cin.tie(0); để đọc nhanh.

Không gian$O(M \cdot N)$

Thời gian$O(4 \cdot M \cdot N)$

Kết quả chạy thật cách 1: bản C++ đúng 100/100 test, chậm nhất khoảng 0.09 giây. Bản Python đúng 100/100 test, chậm nhất khoảng 0.31 giây.

Cách 2Công thức 4 × số cây − 2 × số cặp kề

Nhìn theo hướng ngược lại: nếu các cây đứng riêng lẻ thì mỗi cây cần 4 đoạn rào, tổng là $4 \times$ số cây. Mỗi khi có một cặp cây kề cạnh nhau thì cạnh chung giữa chúng bị đếm 2 lần (1 lần cho mỗi cây) nhưng thật ra không cần rào, nên phải trừ đi 2:

Công thức

$$\text{rào} = 4 \times (\text{số cây}) - 2 \times (\text{số cặp cây kề cạnh})$$ Ví dụ đề: có 13 cây và 8 cặp kề (4 cặp ngang, 4 cặp dọc), nên rào $= 4 \cdot 13 - 2 \cdot 8 = 52 - 16 = 36$ ✓.

Để không đếm trùng, mỗi cây chỉ nhìn sang trái và nhìn lên trên. Như vậy chỉ cần nhớ hàng phía trên (pre) và hàng đang đọc (cur), đếm ngay trong lúc đọc dữ liệu – không cần lưu cả mảnh vườn:

C++▶ Chạy tay từng dòng codeCách 2: đếm số cây và số cặp kề (nhìn trái, nhìn lên) ngay khi đọc, chỉ lưu 2 hàng.

Dữ liệu vào (stdin) – sửa thoải mái5 5 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Khi đọc tới cur[j] thì cur[j - 1] đã là số của hàng hiện tại (vừa đọc ở bước trước), còn pre[j] là số ở hàng trên. cur[0] và mọi pre[j] lúc đầu đều bằng 0 nên cây ở mép trái và hàng đầu tự động không có cặp.
2. Đọc xong một hàng thì chép cur sang pre để chuẩn bị cho hàng sau.
3. Bộ nhớ chỉ còn $O(N)$ thay vì $O(M \cdot N)$ – với bài này thì cả 2 cách đều thừa bộ nhớ, nhưng kỹ thuật "chỉ giữ 2 hàng" rất có ích ở các bài quy hoạch động sau này.

Không gian$O(N)$

Thời gian$O(M \cdot N)$

Kết quả chạy thật cách 2: bản C++ đúng 100/100 test, chậm nhất khoảng 0.07 giây. Bản Python đúng 100/100 test, chậm nhất khoảng 0.25 giây.

Tổng kếtSo sánh 2 cách

Cách	Thời gian	Bộ nhớ	C++	Python
1. Duyệt 4 ô kề	$O(M \cdot N)$	$O(M \cdot N)$	100/100	100/100
2. 4·cây − 2·cặp kề	$O(M \cdot N)$	$O(N)$	100/100	100/100

Ghi chú của mình: tất cả code trong bài đều được chấm thật trên toàn bộ 100 test chính thức (giới hạn 1 giây, đo bằng thời gian CPU). Bài không có subtask vì cách đơn giản nhất cũng đã là $O(M \cdot N)$ – thời gian chủ yếu nằm ở việc đọc $10^6$ số. Cả 2 bản Python cũng qua hết (chậm nhất khoảng 0.31 giây) nhờ đọc toàn bộ input một lần bằng sys.stdin.buffer.read().split().

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇