Một nhà thám hiểm đi vào một mê cung có dạng một hình chữ nhật kích thước MN. Mê cũng được chia thành lưới ô vuông với các hàng được đánh số từ 1 đến M từ trên xuống và các cột được đánh số từ 1 đến N từ trái qua phải. Mê cung có rất nhiều cạm bẫy được đặt ở một số vị trí cố định. Hãy giúp nhà thám hiểm xác định xem liệu có thể đi từ ô (1,1) đến ô (m,n) hay không, nếu được thì phải mất ít nhất là bao nhiêu ngày. Biết rằng ban đầu nhà thám hiểm ban đầu đứng ở lỗi vào là ô (1,1) và phải mất 1 ngày để đi từ một ô bất kì đến một trong 4 ô kề cạnh với nó.

Dữ liệu:

• Dòng đầu tiên ghi hai số nguyên dương M, N cho biết kích thước của mê cung.
• M dòng tiếp theo mỗi dòng chứa N số nguyên mang giá trị 0 hoặc 1 cho biết trạng thái của mê cung, a[i,j]=0 nếu ô (i,j) không có bẫy, a[i,j]=1 nếu ô (i,j) có bẫy.

Kết quả: Đưa ra một số nguyên duy nhất là số ngày ít nhất để nhà thám hiểm vượt qua được mê cung, nếu không thể vượt qua được mê cung thì ghi ra -1.

Giới hạn: M, N ≤ 1000.