Bedao Regular Contest 01 - HGRAPH

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Dạo gần đây do quá lười biếng, chó vàng đã bị chị Hiền lôi đầu ra bắt phải làm việc. Mệt mỏi và chán nản, chó vàng quyết định lại một lần nữa sủi công việc của mình. Nhưng Hiền đã cao tay hơn đi trước một bước, Hiền đã tóm cổ chó vàng nhét vào trong một mê cung, và bắt chó vàng phải nghĩ ra bài mới thì chó mới thoát khỏi mê cung được.

Phận là một con chó, lại bị đàn áp như thế, thật không thể chấp nhận được. Vì thế, chó vàng đã nhờ đến sự trợ giúp của bạn, một lập trình viên cao tay. Bạn hãy giúp chó tìm đường đi thoát khỏi mê cung nhanh nhất có thể.

Mê cung mà chó vàng bị nhốt có thể được biểu diễn dưới dạng một ma trận gồm ~N~ hàng và ~M~ cột. Các hàng được đánh số từ ~1~ đến ~N~ từ trên xuống, các cột được đánh số từ ~1~ đến ~M~ từ trái sang phải. Ô giao giữa hàng thứ ~i~ và cột thứ ~j~ được kí hiệu là ô (~i~, ~j~). Khi đứng ở ô (~i~, ~j~), chó vàng có thể di chuyển sang một trong bốn hướng Bắc, Đông, Nam, Tây, đến một trong các ô (~i - 1~, ~j~), (~i~, ~j + 1~), (~i + 1~, ~j~), (~i~, ~j - 1~) với thời gian di chuyển là một giây.

Một số ô trong ma trận sẽ có cột đá, khi đứng trong một ô có cột đá, chó vàng có thể đạp cột đá để phóng đến một ô cùng hàng hoặc cùng cột, sao cho không có bất kì cột đá nào khác trên đường bay của chó vàng trừ ô xuất phát và ô kết thúc. Chó vàng bay rất nhanh, nên có thể xem thời gian bay là một giây.

Hiện tại chó vàng đang đứng ở ô (~1~, ~1~), để thoát ra khỏi mê cung, chó vàng cần đến được ô (~N~, ~M~). Hãy tìm đường đi nhanh nhất để chó vàng có thể thoát ra khỏi mê cung.

Input

Dòng đầu tiên gồm chứa ~2~ số nguyên ~N~ và ~M~ ~(1 \le N, M \le 1000)~ mô tả ma trận A.

~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên mô tả ma trận, A(i, j) = 1 hoặc 0, tương ứng ở ô (i, j) có cột đá hay không.

Output

In ra một số nguyên là thời gian nhanh nhất để chó vàng có thể thoát ra khỏi mê cung.

Sample Input

4 5
0 1 0 0 0
1 0 0 0 1
1 0 1 0 0
0 0 1 0 0

Sample Output

3

Subtask

  • Subtask 1: 10% số lượng bộ test có ~1 \le N * M \le 10~
  • Subtask 2: 30% số lượng bộ test có ~1 \le N, M \le 100~
  • Subtask 3: 60% số lượng bộ test có ~1 \le N, M \le 1000~

Comments

Please read the guidelines before commenting.


There are no comments at the moment.