Phân tích: Bạn có thể đi con đường của riêng mình

Test Set 1

Trong test set đầu tiên, ta có thể dùng quay lui để xây dựng tất cả các đường đi có thể có từ ô phía tây bắc đến ô phía đông nam của mê cung, rồi kiểm tra xem đường nào thỏa mãn yêu cầu (theo phần Dữ liệu ra, ta biết rằng luôn tồn tại ít nhất một đáp án). Khi tìm được một đường hợp lệ, ta xuất đường đó làm đáp án cho bộ test và dừng việc tìm kiếm.

Test Set 2

Hãy đánh giá số lượng đường đi có thể có từ ô phía tây bắc đến ô phía đông nam. Với một mê cung kích thước \(N \times N\), mọi đường đi hợp lệ đều thực hiện \(N - 1\) bước về phía đông và \(N - 1\) bước về phía nam. Lưu ý rằng thứ tự thực hiện các bước này không quan trọng: sau khi thực hiện tất cả các bước, ta luôn đến ô phía đông nam và trong quá trình đó chắc chắn không ra khỏi mê cung.

Như vậy, ta cần thực hiện tổng cộng \(2N - 2\) bước, trong đó có \(N - 1\) bước về phía đông và \(N - 1\) bước về phía nam, còn thứ tự không quan trọng. Dùng tổ hợp, ta thấy có \(C(2N - 2, N - 1)\) khả năng. Với \(N \le 10\) trong test set 1, có nhiều nhất \(48620\) đường đi cần kiểm tra. Tuy nhiên, trong test set 2, khi \(N = 100\), có \(22750883079422934966181954039568885395604168260154104734000\) (xấp xỉ \(2{,}28 \times 10^{58}\)) đường đi có thể chọn. Con số này quá lớn để xử lý trong giới hạn thời gian, vì vậy ta cần nghĩ đến một lời giải khác.

Ta có thể xem mê cung như một đồ thị, trong đó các ô vuông đơn vị là các đỉnh và có một cạnh nối mỗi cặp đỉnh biểu diễn hai ô kề nhau. Khi đó, thay vì di chuyển giữa hai ô kề nhau, ta di chuyển giữa hai đỉnh tương ứng dọc theo cạnh nối chúng. Vì không được sử dụng lại các bước đi của Lydia, những cạnh mà cô ấy đã sử dụng không còn dùng được đối với ta, nên ta xóa chúng khỏi đồ thị. Sau đó, bài toán tìm một đường đi hợp lệ trở thành bài toán tìm bất kỳ đường đi nào từ đỉnh biểu diễn ô phía tây bắc đến đỉnh biểu diễn ô phía đông nam. Đây là một bài toán đồ thị tiêu chuẩn, có thể giải bằng tìm kiếm theo chiều sâu (DFS) hoặc tìm kiếm theo chiều rộng (BFS) trong thời gian \(O(N^2)\), đủ nhanh để vượt qua test set này.

Test Set 3

Khi \(N \le 50000\), ta phải nghĩ đến một cách tiếp cận khác cho bài toán.

Để giải test set này, ta chỉ cần đảo tất cả các bước trong đường đi của Lydia. Nghĩa là, mỗi khi cô ấy đi về phía đông, ta đi về phía nam; mỗi khi cô ấy đi về phía nam, ta đi về phía đông. Ví dụ, nếu đường đi của Lydia là EESSSESE, đường đi của ta sẽ là SSEEESES.

Hãy tìm hiểu vì sao đường đi đảo này là một đáp án đúng của bài toán.

Trước hết, lưu ý rằng ta vẫn thực hiện \(N - 1\) bước về phía đông và \(N - 1\) bước về phía nam, vì vậy cuối cùng ta sẽ đến ô phía đông nam đúng như yêu cầu và không bước ra ngoài biên của mê cung.

Bây giờ hãy xét vì sao ta không sử dụng lại bất kỳ bước đi nào của Lydia. Giả sử điều này không đúng và ta sử dụng lại một bước đi bắt đầu từ vị trí cách ô phía tây bắc \(X\) bước về phía đông và \(Y\) bước về phía nam, theo một thứ tự nào đó. Nhắc lại rằng thứ tự các bước không quan trọng và có thể có nhiều cách để đến vị trí này, nhưng tất cả đều cần chính xác \(X\) bước về phía đông và \(Y\) bước về phía nam. Bước tiếp theo sẽ là gì? Ta biết bước tiếp theo của Lydia là ký tự thứ \((X + Y + 1)\) trong chuỗi biểu diễn đường đi của cô ấy (đánh số từ \(1\)), còn bước tiếp theo của ta là ký tự thứ \((X + Y + 1)\) trong chuỗi biểu diễn đường đi của ta. Nhưng vì chuỗi đường đi của ta là phiên bản đảo của chuỗi đường đi của Lydia, ta biết rằng hai ký tự thứ \((X + Y + 1)\) trong hai chuỗi sẽ khác nhau; điều này mâu thuẫn với giả sử rằng ta thực hiện cùng một bước tiếp theo. Với lập luận tương tự, ta thấy hai đường đi cũng không sử dụng lại bất kỳ bước đi nào khác trên đường.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng loại — You Can Go Your Own Way.