Bảo vệ nông trang

Tác giả:

Dạng bài

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này. Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm \(N (1 < N \leq 700)\) hàng và \(M (1 \leq M \leq 700)\) cột. Mỗi phần tử của ma trận là độ cao \(H_{ij}\) so với mặt nước biển \((0 \leq H_{ij} \leq 10000)\) của ô \((i,j)\). Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là \(1\) hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ \(X\) không quá \(1\) và chênh lệch tọa độ \(Y\) không quá \(1\).

Input

Dòng 1: Hai số nguyên cách nhau bởi dấu cách: \(N\) và \(M\)
Dòng 2 \(\ldots\) N + 1: Dòng \(i+1\) mô tả hàng \(i\) của ma trận với \(M\) số nguyên cách nhau bởi dấu cách: \(H_{ij}\)

Output

Một số nguyên duy nhất là số lượng đỉnh đồi.

Example

Test 1

Input

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0    
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

Output

Bình luận

2

minhtuanitk20 6:19 p.m. 24 Tháng 1, 2022

vậy tính ra duyệt DFS nhanh && gọn hơn so với BFS nhỉ

3
jumptozero 2:09 p.m. 4 Tháng 6, 2021 ← đã chỉnh sửa →
Mình xin chia sẻ lời giải bài này như sau:

Đầu tiên sẽ tạo một vector dùng để lưu lại các toạ độ có giá trị theo thứ tự giảm dần. Và việc này có ý nghĩa là: Nó sẽ giúp ta tìm được đỉnh đồi, từ đó dùng dfs để ta đánh dấu những ô thuộc về cùng một vùng

Cụ thể như sau, xét hai ví dụ như hình vẽ bên dưới:

Ở hai hình trên, những toạ độ được đóng ô vuông là những đỉnh xuất phát, còn những toạ độ được đóng hình tròn là những toạ độ được đánh dấu sau khi \(dfs\) từ đỉnh xuất phát.

Thì ứng với mỗi toạ độ xuất phát, sau khi dùng \(dfs\) với tiêu chí: "các toạ độ kề với toạ độ \(u\) mà có giá trị nhỏ hơn hoặc bằng \(u\) sẽ được đánh dấu là thuộc về vùng đồi có chứa đỉnh xuất phát đó".

Như vậy, công việc còn lại chỉ là đếm các vùng này mà thôi.

Về ý tưởng dfs , thì đơn giản ở đây: ta chỉ cần xét \(8\) hướng xung quang một toạ độ bất kì:

Và kiểm tra xem nó có vi phạm đường biên hay không là được !

Như vậy là bài toán đã được giải quyết xong

Ps:

Nếu có gì thắc mắc , các bạn cứ comment nhé

Các bạn có thể tham khảo code của mình tại đây
1 phản hồi