Phân tích: Tide Goes In, Tide Goes Out

Có rất nhiều điều diễn ra trong bài toán này và thật khó để theo dõi tất cả. Chỉ có bảy trăm thí sinh giải đúng, nên bạn biết rằng nó không hề dễ! Hãy cùng xem xét.

Điều đầu tiên bạn nên nhận thấy là đây là một bài toán tìm đường đi ngắn nhất. Chúng ta muốn đi từ điểm A (bắt đầu) đến điểm B (lối thoát) nhanh nhất có thể. Có một số thuật toán tìm đường đi ngắn nhất cổ điển; chúng ta sẽ cố gắng áp dụng thuật toán Dijkstra ở đây.

Thuật toán Dijkstra hoạt động trên một đồ thị có trọng số, vì vậy chúng ta cần xác định một tập hợp các đỉnh và các cạnh giữa chúng. Điều này khá dễ dàng - chúng ta coi các ô là các đỉnh và đặt một cạnh giữa mỗi hai ô liền kề. Chúng ta gặp vấn đề khi cố gắng gán trọng số cho các cạnh: chi phí (tính bằng giây) để di chuyển từ ô này sang ô khác không cố định - nó có thể là 1 hoặc 10 giây (và chúng ta chưa đề cập đến vấn đề di chuyển xung quanh trước khi thủy triều bắt đầu rút).

Một thực tế có thể hơi ngạc nhiên là đây không phải là vấn đề đối với thuật toán Dijkstra. Hãy nhắc lại ngắn gọn cách nó hoạt động - nó duy trì một chi phí tạm thời cho mỗi đỉnh, và tại mỗi bước, nó chọn đỉnh có chi phí nhỏ nhất, cố định đó là chi phí thực sự để đến đỉnh đó, và cập nhật các đỉnh lân cận tương ứng. Tất nhiên trong trường hợp của chúng ta, chi phí để đạt được một đỉnh đơn giản là thời gian cần thiết.

Điều này có nghĩa là chúng ta chỉ cần xem xét thời gian đi từ một ô A sang một ô liền kề B một lần, khi chúng ta tính toán lại thời gian đạt đến B do đã cố định thời gian cho A. Nhưng vì chúng ta đã cố định thời gian đạt đến A, chúng ta có thể dễ dàng tính toán mực nước tại thời điểm này - và do đó chúng ta sẽ biết chi phí di chuyển trên cạnh này. (Lưu ý rằng chúng ta có thể bắt đầu di chuyển từ A càng sớm thì việc di chuyển sẽ càng nhanh. Do đó, chúng ta thực sự nên di chuyển càng sớm càng tốt thay vì chờ đợi một thời điểm tốt hơn.)

Chúng ta cũng có các ràng buộc khác. Hãy gọi tên hai trong số đó - mực nước cần thấp hơn ít nhất 50 cm so với trần của ô chúng ta muốn vào, và "điều kiện về khoảng trống" cần được thỏa mãn. Đối với điều kiện sau, chúng ta chỉ cần kiểm tra - điều này không phụ thuộc vào thời gian chúng ta muốn di chuyển - và loại bỏ cạnh khỏi đồ thị nếu điều kiện không được thỏa mãn. Đối với điều kiện trước, chúng ta cần xem lại những gì thuật toán Dijkstra cần. Chi phí di chuyển cạnh AB được sử dụng để xác định đường đi ngắn nhất đến B đi qua A và sau đó trực tiếp qua cạnh AB đến B. Nếu chúng ta thực sự muốn đi theo con đường này, và mực nước quá cao để vào B khi chúng ta đến A, chúng ta chỉ có một lựa chọn - chúng ta phải đợi cho đến khi mực nước giảm xuống \(C_B - 50\) trước khi di chuyển. Hãy nhớ rằng điều này có thể khiến chúng ta phải kéo thuyền kayak!

Tất cả những điều này có nghĩa là chúng ta có thể tính toán chi phí của mỗi cạnh tại thời điểm chúng ta cần nó, và chúng ta sẽ có một giải pháp hoàn chỉnh cho bài toán nếu không có khả năng di chuyển xung quanh trước khi thủy triều bắt đầu rút. Một người có thể muốn giải quyết vấn đề này bằng một giai đoạn tiền xử lý, nơi chúng ta sử dụng tìm kiếm theo chiều rộng (BFS) để tìm tất cả các ô có thể đến được từ điểm bắt đầu trong thời gian bằng 0.

Tuy nhiên, một giải pháp đơn giản hơn để lập trình là đưa giai đoạn này vào thuật toán Dijkstra. Tất cả những chuyển động bổ sung này có nghĩa là nếu chúng ta muốn đi qua cạnh AB, chúng ta đang ở A tại thời điểm 0, và B có thể truy cập được từ A tại thời điểm 0, thì chi phí của việc di chuyển này là 0 - vì chúng ta có thể thực hiện nó trước khi thủy triều bắt đầu rút. Điều này có nghĩa là chúng ta thêm một điều kiện bổ sung trong hàm tính toán chi phí, và chúng ta đã hoàn thành!

Lưu ý rằng kết quả ở đây chỉ là một bản cài đặt tiêu chuẩn của thuật toán Dijkstra, với tất cả logic cụ thể của bài toán được đưa vào hàm tính toán trọng số của một cạnh nhất định tại thời điểm cần thiết.

Dựa trên phân tích chính thức của Google Code Jam.