TREASURE - Đảo kho báu
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: mrtan_lovelife

Mùa hè vừa rồi, Misaki đến chơi nhà bạn của mình ở một hòn đảo đẹp tuyệt vời. Cô cùng bạn mình có những chuyến vui chơi rất hấp dẫn trên đảo như tắm biển, chơi bóng chuyền, tham quan đảo... Trong thời gian ở đây, Misaki tìm thấy một hòn đảo nhỏ gần nơi của mình, cô liền bơi thuyền đến đó và bắt đầu khám phá. Phát hiện ra hòn đảo này còn rất hoang sơ và hầu như chưa có người đặt chân đến, Misaki quyết định chôn một kho báu bí mật ở đây, sau đó cô trở về tiếp tục cuộc vui chơi.

Cuối đông, Misaki có dịp trở lại hòn đảo của bạn mình, cô định sẽ quay lại hòn đảo mình đã khám phá ra để lấy lại kho báu. Nhưng bây giờ đang là mùa đông nên đường đến hòn đảo đó bị bao phủ bởi rất nhiều tảng băng, cô không thể đến đó ngay được. May thay, vì là cuối mùa đông nên các tảng băng đang tan ra. Mỗi ngày, phần băng tiếp xúc với nước biển hoặc các hòn đảo sẽ bị tan ra trước đến khi cả tảng băng bị tan hết. Có thể xem bản đồ hòn đảo ban đầu và đảo kho báu là một trục tọa độ với tọa độ đảo ban đầu là (u1,v1) và đảo kho báu là (u2,v2), giả sử các tảng băng có thể được chia thành các ô vuông nhỏ của trục. Nếu ngày hôm trước tại ô (i, j) là nước biển hay đảo thì sang ngày hôm sau, băng tại bốn ô liền kề (i-1, j), (i+1, j), (i, j-1), (i, j+1) sẽ tan thành nước biển. Nếu Misaki đang ở tại ô (i, j), cô ấy cũng chỉ có thể đi sang một trong bốn ô liền kề (i-1, j), (i+1, j), (i, j-1), (i, j+1). Bạn hãy giúp Misaki tính xem cô phải đợi bao nhiêu ngày để có thể đến được đảo kho báu nhé. Nếu bạn giải được, cô ấy sẽ cho bạn biết kho báu cô ấy chôn ở đó là gì! wink (Đùa thôi :v)

Yêu cầu: Cho bản đồ của các tảng băng và tọa độ hòn đảo ban đầu cũng như đảo kho báu, bạn hãy xác định xem cần bao nhiêu ngày để các tảng băng tan ra để có ít nhất một đường đi từ đảo ban đầu đến đảo kho báu.

Dữ liệu nhập: 

  - Dòng thứ nhất chứa 2 số nguyên N,M là số dòng và cột của bản đồ (1 ≤ N,M ≤ 1000).

  - N dòng tiếp theo, mỗi dòng chứa M số là các số 0,1 với 0 là không có băng và 1 là có. Tại vị trí đảo cũng có giá trị 0.

  - Dòng cuối cùng chứa 4 số nguyên là u1,v1,u2,v2 với u1,v1 là tọa độ của đảo ban đầu và u2,v2 là tọa độ của đảo kho báu (1 ≤ u1,u2 ≤ N , 1 ≤ v1,v2 ≤ M).

Dữ liệu xuất: 

  Gồm 1 số nguyên duy nhất là số ngày cần phải đợi để có đường đi từ đảo ban đầu đến đảo kho báu.

Ví dụ

  • input
    5 7
    0 1 1 1 1 1 0
    1 1 1 1 1 1 1
    1 1 1 0 1 1 1
    1 1 1 1 1 1 1
    0 1 1 1 1 1 0
    1 1 3 4
    output
    2

Bản đồ băng sau các ngày:

Ngày thứ nhất:                                          Ngày thứ hai:

0  0  1  1  1  0  0                                       0  0  0  0  0  0  0

0  1  1  0  1  1  0                                       0  0  0  0  0  0  0

1  1  0  0  0  1  1                                       0  0  0  0  0  0  0

0  1  1  0  1  1  0                                       0  0  0  0  0  0  0

0  0  1  1  1  0  0                                       0  0  0  0  0  0  0

Back to Top