[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
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ị.
Ví dụ: '#' là ô cấm; '.' là ô tự do
Input:
8 10
########
.......#
.#.#.#.#
.#####.#
#....#.#
#.##.#.#
#.##...#
#.#.##.#
#.#.##.#
#.....##
Output:
29
Em xin ý tưởng thôi không cần code đâu ạ.
Ví dụ: '#' là ô cấm; '.' là ô tự do
Input:
8 10
########
.......#
.#.#.#.#
.#####.#
#....#.#
#.##.#.#
#.##...#
#.#.##.#
#.#.##.#
#.....##
Output:
29
Em xin ý tưởng thôi không cần code đâu ạ.
