Phân tích

Một số kiểm tra ban đầu

Trước tiên tính hai giá trị: độ dài \(L_i\) của một đường đi ngắn nhất bất kỳ từ đầu đến cuối (bằng BFS), và khoảng cách Manhattan \(M\) từ đầu đến cuối khi bỏ qua tường. Từ đó, ta phát hiện ngay một số trường hợp bất khả thi:

• Ta chỉ có thể dỡ tường nên không thể tăng độ dài đường đi ngắn nhất vượt \(L_i\). Vì vậy nếu \(L_i<D\) thì không có lời giải.
• Tương tự, nếu \(M>D\), dỡ tường cũng không giúp được; ngay cả mê cung trống chỉ có một đường biên vẫn có đường đi ngắn nhất dài hơn \(D\).
• Nếu tính chẵn lẻ của \(L_i\) và \(D\) khác nhau thì không có lời giải. Độ dài mọi đường đi giữa hai ô cố định có cùng tính chẵn lẻ, vì mỗi bước làm đảo tính chẵn lẻ của tổng chỉ số hàng và cột.

Điều đáng ngạc nhiên là trong mọi trường hợp còn lại, luôn tồn tại lời giải. Phần còn lại của bài toán là đưa ra một chứng minh xây dựng cho sự thật đó.

Một nhận xét then chốt

Ta muốn dỡ tường để đổi độ dài đường đi ngắn nhất hiện tại \(L\) thành \(D\). Mấu chốt là nhận ra rằng ta luôn có thể dỡ một tường sao cho đường đi ngắn nhất mới có độ dài \(L\) hoặc \(L-2\). Chứng minh hơi khó, nhưng trước hết ta bàn trực giác (chứng minh hình thức nằm cuối bài phân tích).

Xét một thành phần liên thông của các ô tường. Thành phần đó hoặc chứa biên, hoặc không. Chọn trong thành phần một tường \(W\) xa biên nhất có thể; nếu thành phần không chứa biên, chọn một tường tùy ý trong thành phần làm mốc. Dùng việc mọi ô trống liên thông và không có hai tường chỉ tiếp xúc ở góc, ta thấy lân cận \(3\times3\) của \(W\), xét đến đối xứng, có một trong các dạng sau (# là tường, . là ô trống, ? có thể là bất kỳ):

...  ?#?  ?##
.W.  .W.  .W#
...  ...  ..?

Xét lần lượt từng trường hợp. Ta sẽ chỉ ra rằng nếu đường đi ngắn nhất đi qua lân cận \(3\times3\) của \(W\), việc dỡ \(W\) làm độ dài giảm nhiều nhất 2:

• \(W\) không có láng giềng nào là tường: đường duy nhất được rút ngắn là đường vòng quanh \(W\). Dỡ \(W\) rút ngắn 2 bước vì giờ có thể đi thẳng qua \(W\).
• \(W\) có một láng giềng là tường: giả sử là trường hợp vẽ trên và đường ngắn nhất đi từ góc trên trái vòng qua phía dưới đến góc trên phải. Dỡ \(W\) một lần nữa rút ngắn 2 bước.
• \(W\) có hai láng giềng là tường: dỡ \(W\) không rút ngắn đường đi. (Ta vẫn cần trường hợp này vì việc dỡ tường ấy có thể mở đường cho những tường khác trở thành dỡ được.)

Hình dưới minh họa ba trường hợp trên. Để đơn giản, hình giả sử mọi ? đều là tường, nhưng lập luận đúng bất kể chúng là gì.

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_114b4991.png

Vì vậy, để giải bài, ta cứ liên tục dỡ tường khỏi bản đồ (nhớ rằng dỡ một tường có thể làm tường khác trở thành dỡ được) cho đến khi đường đi ngắn nhất bằng \(D\). Với Test Set nhỏ, ta có thể liên tục quét bản đồ tìm tường dỡ được, dỡ một tường, rồi tiếp tục cho đến khi đạt độ dài yêu cầu.

Với Test Set lớn, quét bản đồ lặp đi lặp lại quá chậm. Ta cần tìm trước một danh sách thứ tự các tường cần dỡ, rồi tìm kiếm nhị phân số lượng tường đầu danh sách phải dỡ để thu được độ dài yêu cầu. Để lập danh sách, quét bản đồ một lần rồi khởi tạo hàng đợi chứa mọi tường dỡ được. Mỗi lần chọn tường tiếp theo để dỡ, kiểm tra các láng giềng của nó xem tường nào mới trở thành dỡ được và thêm chúng vào cuối hàng đợi. Ta cũng phải kiểm tra các láng giềng có thể vừa trở thành không dỡ được và xóa chúng khỏi hàng đợi. Ví dụ, nếu một thành phần liên thông chỉ là hình vuông \(2\times2\), ban đầu cả bốn tường đều dỡ được; nhưng sau khi dỡ một tường, chỉ hai trong ba tường còn lại dỡ được. Do đó đôi lúc phải xóa một tường khỏi hàng đợi, rồi có thể chèn lại về sau.

Phương pháp này chỉ quét toàn bản đồ một lần, sau đó làm thêm lượng công việc hằng số cho mỗi tường được dỡ, tức tổng \(O(N)\) theo số ô, đủ nhanh cho Test Set lớn. Cuối cùng nó dỡ mọi tường, ngoại trừ khả năng để lại một đường biên cực dày không dỡ được. Đường biên này không quan trọng vì dỡ nó cũng không thay đổi đường đi ngắn nhất.

Chứng minh hình thức

Như trước, gọi \(L_i\) là độ dài đường ngắn nhất ban đầu và \(M\) là khoảng cách Manhattan. Ta khẳng định bài toán giải được với mọi \(D\) có cùng tính chẵn lẻ với \(L_i\) và nằm giữa \(L_i\) và \(M\). Chỉ cần chứng minh luôn có thể xóa một tường mà mê cung vẫn hợp lệ và độ dài đường ngắn nhất hiện tại \(L\) giảm không quá 2.

Xét một thành phần liên thông bất kỳ của các tường. Nếu nó chứa biên ngoài, gọi \(B\) là tập các tường trên biên ngoài. Nếu không, cho \(B\) là một tường tùy ý trong thành phần. Gọi \(A\) là một tường trong thành phần, kề một ô trống và cách \(B\) xa nhất có thể (khoảng cách đo bằng đường đi nằm trong thành phần). Ta sẽ xóa \(A\).

Việc này thêm một ô trống kề một ô trống khác, nên mọi ô trống vẫn liên thông. Tiếp theo cần chứng minh nó không thể khiến hai tường chỉ chạm nhau ở góc. Phản chứng: giả sử \(X,Y\) là hai tường cùng kề \(A\) và một ô trống \(Z\). \(Z\) và \(A\) được nối qua các ô trống, nên sau khi xóa \(A\), \(X,Y\) không thể còn được nối bằng các ô tường. Do đó một trong \(X,Y\) phải xa \(B\) hơn \(A\). Nhưng \(X,Y\) không thuộc biên ngoài, trước khi xóa \(A\) chúng nối với \(B\), và chúng kề \(Z\), tạo ra mâu thuẫn.

Cuối cùng, cần chứng minh xóa \(A\) không thể làm hai ô trống gần nhau hơn quá hai bước. Khả năng duy nhất là \(A\) kề hai ô trống đối diện \(X,Y\) và hai tường \(W,Z\). Như trên, \(X,Y\) liên thông, nên sau khi xóa \(A\), \(Z,W\) không thể được nối bằng tường. Điều này dẫn đến cùng mâu thuẫn. \(W,Z\) có thể không kề trực tiếp một ô trống, nhưng chúng kề một thứ khác \(A\) mà bản thân thứ ấy kề ô trống. Hoặc \(W\), hoặc \(Z\), hoặc ô kề đó sẽ mâu thuẫn với cách chọn \(A\). Lưu ý rằng mệnh đề then chốt này sai nếu cho phép các tường chỉ chạm ở góc, nhưng đề bài đã cấm điều đó.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - World Finals - Map Reduce, kho Google Coding Competitions (Apache-2.0).