Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
081. MÊ CUNG Bản đồ mê cung có dạng hình chữ nhật kích thước mxn được chia thành lưới ô vuông đơn vị bằng các đường song song với các cạnh (m hàng, n cột). Mỗi ô vuông của bản đồ được đánh dấu hoặc là ô cấm, hoặc là ô tự do. Từ một ô tự do có thể di chuyển sang các ô tự do có chung cạnh với nó. Không được phép di chuyển vượt khỏi biên của mê cung. | 081. MÊ CUNG Bản đồ mê cung có dạng hình chữ nhật kích thước mxn được chia thành lưới ô vuông đơn vị bằng các đường song song với các cạnh m hàng n cột . Mỗi ô vuông của bản đồ được đánh dấu hoặc là ô cấm hoặc là ô tự do. Từ một ô tự do có thể di chuyển sang các ô tự do có chung cạnh với nó. Không được phép di chuyển vượt khỏi biên của mê cung. Mê cung được thiết kế khá đặc biệt giữa hai ô tự do bất kỳ chỉ có duy nhất một cách di chuyển từ ô này đến ô kia mà trong quá trình di chuyển không đi tới bất kỳ ô nào quá một lần. Tại tâm của mỗi ô tự do đều có một cái móc. Trong mê cung có hai ô tự do đặc biệt mà nếu bạn nối được hai cái móc ở hai ô đó bằng một sợi dây thừng tất nhiên phải nối qua các móc của các ô trung gian thì cánh cửa bí mật của mê cung sẽ tự mở ra. Vấn đề đặt ra là phải chuẩn bị một sợi dây thừng với độ dài ngắn nhất đảm bảo cho dù hai ô đặc biệt có nằm ở vị trí nào trong mê cung bạn vẫn có thể nối được hai cái móc ở hai ô đó bằng sợi dây đã chuấn bị. Dữ liệu Vào từ file văn bản LABYR.INP Dòng đầu tiên chứa hai số n m 3 m n 1000 Các dòng tiếp theo mô tả mê cung dòng thứ i trong số m dòng tiếp theo chứa n ký tự mỗi ký tự chỉ là hoặc . . Trong đó ký tự cho biết ô ở vị trí tương ứng là bị cấm còn ký tự . cho biết ô ở vị trí tương ứng là tự do 1 i m . Kết quả Ghi ra trên một dòng của file văn bản LABYR.OUT độ dài của sợi dây thừng cần chuẩn bị. Ví dụ LABYR.INP LABYR.OUT . 0 LABYR.INP LABYR.OUT 8 10 . . . . . . . . . . . . . . . . . . . . 29 91 082. DU LỊCH KIỂU ÚC Một khu thắng cảnh gồm n điểm đánh số từ 1 tới n n 200 và m đường đi hai chiều nối giữa các cặp địa điểm đó. Giữa hai cặp địa điểm có nhiều nhất là một đường đi trực tiếp. Có hai địa điểm đặc biệt A và B. Một Tour du lịch là một hành trình của du khách Trước hết là đáp máy bay xuống địa điểm A sau đó đi bộ theo các đường hai chiều đã cho để tới địa điểm B và lại đi bộ quay trở về địa điểm xuất phát A để rồi quay về bằng máy bay. Để tránh sự nhàm chán cho du khách hành trình không được đi qua .
