Đồ thịHàng đợi
Mô tả
Trung tâm dữ liệu VNG sắp mở rộng hệ thống máy chủ. Kỹ sư mạng cần đi một tuyến cáp quang từ tủ rack nguồn đến tủ rack đích trên mặt sàn kỹ thuật. Mặt sàn được chia thành các ô vuông, mỗi ô có thể đi qua được hoặc bị chắn bởi các thiết bị nặng (không đi qua được).
Bạn chỉ được di chuyển theo bốn hướng: lên, xuống, trái, phải. Hãy tìm số bước đi ít nhất từ ô nguồn đến ô đích. Nếu không thể đến được ô đích, trả về -1.
Đầu vào
Hàm nhận ba tham số:
grid: danh sách các chuỗi, mỗi chuỗi là một hàng của lưới. Ký tự'.'là ô trống,'#'là ô bị chắn,'S'là ô nguồn,'E'là ô đích.n: số nguyên, số hàng của lưới (1 ≤ n ≤ 1000).m: số nguyên, số cột của lưới (1 ≤ m ≤ 1000).
Đầu ra
Trả về một số nguyên là số bước đi ít nhất từ 'S' đến 'E', hoặc -1 nếu không có đường đi. Số bước được tính là số lần di chuyển (không tính ô xuất phát).
Ràng buộc
- 1 ≤ n × m ≤ 10^6
- Lưới có đúng một
'S'và một'E'. - Mỗi ô chỉ được đi qua một lần.
Ví dụ
Ví dụ 1:
Lưới:
S... .#.. .#.. ...E
Một đường đi ngắn nhất là S → phải → phải → phải → xuống → xuống → xuống → E, tổng cộng 6 bước.
Kết quả: 6