Tìm đường đi ngắn nhất trong mê cung

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 977M
Author:
TICHPX
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Một mê cung được cho bởi một ma trận chứa các số 0 và 1 trong đó ô nào chứa số 0 là có thể đi qua được còn chứa số 1 là vật cản không thể đi qua được. Mèo Toto là một con rô bốt rất thông minh nó được thả vào trong mê cung để săn lùng những con chuột. Bằng trí tuệ nhân tạo siêu phàm mèo Toto đã định vị được trong mê cung có một vị trí có chuột. Nhưng người lập trình cho nó chưa lập trình được thuật toán tìm đường đi ngắn nhất từ vị trí của nó tới chuột. Bạn hãy lập trình giải bài toán này giúp mèo Toto nhé

Input

Dòng đầu chứa 2 số nguyên dương n và m tương ứng với số hàng và số cột của mê cung \((1<=n,m<=1000)\)

n dòng tiếp theo mỗi dòng chứa m số 0 hoặc 1

Dòng cuối cùng là vị trí của mèo Toto và vị trí của chuột trong mê cung hai vị trí của mèo có thể là 0 hoặc 1 còn chuột thì luôn là 0, quá trình di chuyển chỉ đi sang những ô 0

Output

Một số nguyên là số bước đi ngắn nhất từ vị trí mèo Toto đến vị trí chuột biết rằng mèo chỉ đi được theo hướng ngang hoặc dọc của 4 láng giềng trên, dưới hoặc phải, trái. Trong trường hợp không đi được in ra -1. Biết rằng mèo chỉ đi được trong mê cung thôi

enter image description here

Ví dụ 1

Input

3 3
0 1 0
0 0 0
1 0 0
1 1 3 3

Output

4

Ví dụ 2

Input

3 3
0 1 0
0 1 1
1 1 0
1 1 3 3

Output

-1
tichpx

Comments


  • 3
    TICHPX  commented on Sept. 13, 2020, 2:23 p.m.

    Chỉ số hàng trước cột sau


  • 0
    Phuc_CNTT3_K60  commented on Sept. 11, 2020, 3:39 p.m.

    Em thấy đề bài ghi là "cả hai vị trí này đều chứa số 0" mà


    • 1
      TICHPX  commented on Sept. 13, 2020, 2:24 p.m.

      Vị trí xuất phát và kết thúc luôn chứa số 0


      • 0
        Phuc_CNTT3_K60  commented on Sept. 13, 2020, 2:42 p.m.

        Em in test 2 3 ra thì lại thấy mèo đi từ 1


        • 3
          TICHPX  commented on Sept. 14, 2020, 3:28 a.m.

          ồ vậy à, chắc bộ test vớ vẩn, giờ sửa lại đề vậy


  • 0
    Phuc_CNTT3_K60  commented on Sept. 11, 2020, 3:38 p.m.

    Thầy ơi bài này mèo có thể đi từ ô 1 ạ @@


  • 0
    An_CNTT1_K60  commented on Sept. 11, 2020, 7:19 a.m.

    Cho em hỏi là 2 điểm đầu và cuối thì chỉ số hàng hay chỉ số cột được viết trước ạ?