Cho một mê cung, mê cung được làm bởi các cell và được kết nối với nhau bằng các đường 1 chiều. Người ta nhốt những con chuột vào trong mỗi cell và được đào tạo. Nhiệm vụ của bạn là in ra số lượng chuột thoát ra khỏi mê cùng trong thời gian T.
Giải thuật:
Bài này là bài tìm đường đi ngắn nhất từ các cell đến lối ra. Các bạn có thể cài đặt BFS tại vị trí cổng thoát ra và đảo chiều đường đi để tìm thời gian tối thiểu đi từ lối ra đến các cell.
Đến đây các bạn sẽ nghĩ rằng làm sao để cài đặt Dijsktra bằng BFS. Cũng giống như Dijisktra các bạn cũng define 1 mảng khoảng cách ngắn nhất từ đỉnh ban đầu đến các đỉnh còn lại là vô cùng
Sau đó thay vì điều kiện của BFS bình thường là nếu chưa thăm thì đánh dấu đã thăm và không cho vào Queue nữa, thì BFS bằng Dijsktra sẽ luôn luôn kiểm tra các cell đã thăm, nếu tồn tại một khoảng cách tối ưu hơn sẽ cập nhật lại nó.
Về cơ bản cài Dijsktra bằng BFS sẽ lâu hơn là cài thẳng Dijsktra vì vậy người ta có một khái niêm về hàng đợi ưu tiên (Priority Queue) để tăng tốc thuật toán này. Nếu muốn tìm hiểu search Wiki :D
Giải thuật:
Bài này là bài tìm đường đi ngắn nhất từ các cell đến lối ra. Các bạn có thể cài đặt BFS tại vị trí cổng thoát ra và đảo chiều đường đi để tìm thời gian tối thiểu đi từ lối ra đến các cell.
Đến đây các bạn sẽ nghĩ rằng làm sao để cài đặt Dijsktra bằng BFS. Cũng giống như Dijisktra các bạn cũng define 1 mảng khoảng cách ngắn nhất từ đỉnh ban đầu đến các đỉnh còn lại là vô cùng
Sau đó thay vì điều kiện của BFS bình thường là nếu chưa thăm thì đánh dấu đã thăm và không cho vào Queue nữa, thì BFS bằng Dijsktra sẽ luôn luôn kiểm tra các cell đã thăm, nếu tồn tại một khoảng cách tối ưu hơn sẽ cập nhật lại nó.
Về cơ bản cài Dijsktra bằng BFS sẽ lâu hơn là cài thẳng Dijsktra vì vậy người ta có một khái niêm về hàng đợi ưu tiên (Priority Queue) để tăng tốc thuật toán này. Nếu muốn tìm hiểu search Wiki :D
Solution C++4.3.2