[DFS và BFS] [USACO] [SPOJ] PWALK

Đề bài
Hướng làm: Do giữa hai đồng cỏ bất kì luôn có duy nhất một đường đi nên việc ta phải làm là tìm đường đi ấy và xuất ra độ dài của nó :)
Code

[DFS và BFS] [SPOJ] ADS

Đề bài
Hướng làm của traitaodo
Hệ quả: Số chu trình cơ sở của đồ thị là k+m-n với k là số lượng thành phần liên thông trong đồ thị, m là số cạnh còn n là số đỉnh. Chứng minh công thức này đã có ở phần Hướng làm ở trên
Code

[DFS và BFS] [USACO] [SPOJ] VBGRASS

Đề bài
Cách làm
Coi các đỉnh là các ô '#', các cạnh là các đường đi giữa các ô '#' với nhau, đáp án là số lượng thành phần liên thông
Code

[DFS và BFS] [Tìm kiếm nhị phân] [Quy hoạch động] [NTUCoder] TREASURE

Đề bài
Hướng làm của mình
Chặt nhị phân số ngày, mỗi lần chặt DFS thử xem có đến được đảo kho báu không.
Cái chính là ta phải tìm số ngày để băng một vùng nào đó tan ra :)
Để tính được, ta dùng thuật sau của AresGod:
push những ô không là băng ban đầu vào queue , gọi a[u][v] là số ngày ít nhất để ô (u,v) tan (khởi tạo = inf) -> BFS từ những ô trong queue đến 4 ô liền kề, ô nào có a[u][v] hiện tại lớn hơn thì cập nhật lại rồi push ô vào đó vào queue tiếp , khi nào xong sẽ xây được mảng a
Hướng làm của BTC
Code

[DFS và BFS] [Dijkstra] [USACO] [SPOJ] VMUNCH

Đề bài
Hướng làm theo BFS
Hướng làm theo Dijkstra
Bài toán có thể phát biểu lại như sau: Tìm đường đi ngắn nhất từ B đến C mà chỉ đi qua các ô có cỏ :)
Code