mazemaze - Mê cung
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: admin

Mê cung A là một bảng gồm m dòng và n cột. Trong đó:

      - A[i][j] = 0: ô không có bẫy

      - A[i][j] = 1: ô có bẫy.

Một người xuất phát tại vị trí (u, v) muốn thoát khỏi mê cung một cách an toàn, người đó thoát ra khỏi mê cung khi vị trí của anh ta là ở biên của mê cung. Hãy giúp anh ta tìm một hành trình ngắn nhất để thoát khỏi mê cung.

Dữ liệu vào

      - Dòng 1 chứa hai số m và n

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

      - Dòng cuối cùng chứa hai số u, v

Kết quả ra:

      - Nếu không có đường đi thì ghi ra -1

      - Ngược lại:

+ Dòng 1 lưu k - độ dài ngắn nhất của hành trìn

+ k dòng tiếp theo, mỗi dòng lưu 2 số là tọa độ của đường đi

Ví dụ

  • input
    3 4
    1 0 1 0
    1 0 0 1
    1 1 1 1
    2 2
    output
    1
    1 2
Back to Top