[DFS và BFS] [SPOJ] POUR1

Đề bài
Hướng làm
BFS theo từng trạng thái của hai bình, khi BFS đánh dấu lại số thao tác để in ra khi cần, cũng như tránh xét một thao tác nhiều lần.
Code

[Chưa hoàn thiện] [DFS và BFS] [VOI] [SPOJ] ROBOCON

Đề bài
Hướng làm:
Tưởng bài này giống bài QBAGENTS, tuy vậy do giới hạn quá lớn nên ta không thể dùng mảng 5 chiều để quy hoạch động được.
Cách làm có tham khảo bên onlylove97
Loang lần lượt từng con robot cho để biết tại thời điểm t các con robot có thể ở vị trí nào, nếu có một ô mà cả hai có thể gặp nhau thì dừng loang, in ra t. Lưu ý các ô có thể đi qua đi lại nhiều lần.
Code (90 điểm SPOJ)

[DFS và BFS] [Quy hoạch động] [Mảng 3 chiều] [SPOJ] QBAGENTS

Đề bài
Hướng làm:
Tham khảo vnspoj.blogspot.com
Gọi F[u,v,k]  là thời gian min để người 1 đến u, người 2 đến v và đến lượt người k đi tiếp. Loang từ F[s,t,1], mỗi lượt luân phiên nhau từng người. Ban đầu khởi  tại F[i,j,k] =maxValue. Kết quả là min(F[u,u,1]). (tùy từng cách code là cộng tiếp thời gian luân phiên hay cộng thời gian theo lượt hai người mà F[u,u,1]/2 hay F[u,u,1]).Code

[DFS và BFS] [Tìm kiếm nhị phân] [USACO] [SPOJ] MTWALK

Đề bài
Hướng làm:
Chặt nhị phân kết quả, sau đó DFS thử xem có đi được không.
Tuy vậy việc kiểm tra độ cao chênh lệch của đường đi quá phức tạp, nên với mỗi độ cao nhỏ nhất, ta tìm độ cao lớn nhất tương ứng với kết quả mình đang xét, sau đó tìm đường đi có độ cao nằm giữa khoảng này (phần này mình tham khảo bên kienthuc24h)
Mình không chặt nhị phân trong code do kết quả cứ ra sai.
Code

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

Đề bài
Hướng làm:
Tìm các thành phần liên thông có cùng độ cao trong bảng, sau đó kiểm tra xem thành phần liên thông đó có phải là đỉnh đồi hay không bằng cách kiểm tra độ cao của các thành phần liên thông liền kề.
Cách làm này mình có tham khảo blog của traitaodo 
Code

[DFS và BFS] [VOI] [SPOJ] STABLE

Đề bài
Hướng làm:
- Sử dụng mảng a làm ma trận kề để tránh dữ liệu lặp, đồng thời chuyển thành danh sách kề để giảm độ phức tạp của BFS.
- Dùng BFS tìm số đường đi ngắn nhất đến từng đỉnh, nếu tìm được 2 đường đi ngắn nhất thì tăng biến đếm, cộng thêm nhận xét từ test ví dụ: nếu u ổn định mà u nằm trên đường đi ngắn nhất từ s đến v thì v ổn định, ta giải được bài này.
- Do trên SPOJ có thêm vài giới hạn về bộ nhớ nên ta phải dùng con trỏ để giảm bộ nhớ sử dụng, cũng như loại bỏ mảng a ở trên (thay thế bằng hàm found).
Code

[Chưa hoàn thiện] [DFS và BFS] [VOI] [SPOJ] STNODE

Đề bài
Hướng làm được 83,33 điểm
BFS tìm 1 đường đi ngắn nhất bất kì từ s đến t, sau đó bỏ dần từng đỉnh rồi DFS thử xem có đến được không.
Thuật chuẩn theo đồn đoán trên mạng là dùng luồng, nhưng cách cài đặt rất phức tạp nên ta sẽ cài sau :)
Code

[DFS và BFS] [Tham lam] [vCoder] [SPOJ] V8ORG

Đề bài
Hướng làm:
DFS từng phần tử như sau:
- Duyệt hết tất cả các thành viên "con"
- Nếu số thành viên "con" của nó vẫn lớn hơn k thì bắt giữ thành viên đó, cập nhập lại số "con" của các thành viên chỉ huy thành viên đó.
Chứng minh đã có trong blog của traitaodo
Code

[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