PL - Đường đi ngắn nhất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: duytoannguyenledh

Một lâu đài có dạng một hình chữ nhật được chia ra làm NM phòng (xem hình 1).

3 3 6 7 11
3 2 1 1 3
3 2 2 1 1
2 1 2 2 1

Hình 1.

Một nhà thám hiểm bắt đầu từ phòng (1,1) muốn di chuyển đến phòng (N,M) tuân thủ qui tắc sau:

  • Trên sàn của mỗi phòng có viết một số huyền bí là số nguyên trong khoảng từ 1 đến 13. Khi nhà thám hiểm có thể lựa chọn một trong tám hướng di chuyển (song song với các bức tường hoặc theo các đường chéo) lập tức anh ta được di chuyển theo hướng đó đi một số lượng phòng đúng bằng số viết trên sàn nhà theo hướng đã chọn. Nếu như điều đó không thực hiện được (khi số lượng phòng theo hướng lựa chọn là nhỏ hơn số viết trên sàn) thì nhà thám hiểm vẫn ở nguyên vị trí và buộc phải lựa chọn hướng dịch chuyển khác.
  • Không được di chuyển hai lần trong cùng một phương theo cùng một hướng.

Ví dụ: Xét lâu đài trong hình 1, các số trên mặt sàn của mỗi phòng được cho trong ô tương ứng. Nếu nhà thám hiểm đang đứng ở phòng (3, 3) trong lâu đài (có 54 phòng) thì anh ta có thể di chuyển đến các phòng (1;1), (3;1), (1;3), (5;1), và (5;3). Để di chuyển từ phòng (3, 2) đến phòng (5,4) sử dụng hai lần dịch chuyển, nhà thám hiểm không được di chuyển đến ô (4,3) rồi từ (4,3) đến (5,4), bởi vì như vậy đã di chuyển trong cùng một phương theo cùng một hướng, mà cần di chuyển đến ô (2,1) và từ đó đến (5,4).

Yêu cầu: Tìm cách di chuyển từ ô (1,1) đến ô (N,M) sau ít lần dịch chuyển nhất.

Dữ liệu: :

  • Dòng đầu tiên chứa hai số nguyên N, M, tương ứng là số phòng theo chiều ngang và theo chiều đứng của sơ đồ toà lâu đài (1 ≤ N, M ≤ 1000).
  • Dòng thứ i trong số M dòng tiếp theo chứa dãy N số nguyên là các số viết trên dãy phòng ở dòng thứ i của toà lâu đài.

Các số trên cùng dòng được viết cách nhau bởi dấu cách.

Kết quả: Ghi ra  số bước dịch chuyển ít nhất. Ghi -1 nếu không có cách di chuyển đến ô (N, M).

Ví dụ

  • input
    5 4
    3 3 6 7 11
    3 2 1 1 3
    3 2 2 1 1
    2 1 2 2 1
    output
    4
Back to Top