Rào cây kiểu Bờm
Đề 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ó.
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 036Giả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.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
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.
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):
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.
- 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ướngklà(i + dx[k], j + dy[k]). - 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 trongmainvừa không tự bằng 0, vừa dễ tràn bộ nhớ ngăn xếp. - Đá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ùnglong longcho chắc tay. - Input có tới $10^6$ số nên nhớ
ios::sync_with_stdio(0); cin.tie(0);để đọc nhanh.
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:
Để 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:
- 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ònpre[j]là số ở hàng trên.cur[0]và mọipre[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. - Đọc xong một hàng thì chép
cursangpređể chuẩn bị cho hàng sau. - 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.
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 |
sys.stdin.buffer.read().split().