LINE - Trò chơi Line
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: ngoclannt

Trò chơi Line là trò chơi di chuyển các viên bi trong một hình vuông 9 x 9 ô. Bi được ăn khi tạo thành các hàng, cột, đường chéo gồm 5 viên bi liên tiếp cùng màu.

        Một thuật toán được sử dụng trong trò chơi là tìm đường đi để di chuyển một viên bi. Giả sử trò chơi Line tổng quát có n dòng, n cột. Đánh số các dòng từ 1 đến n theo thứ tự từ trên xuống dưới, đánh số các cột từ 1 đến n theo thứ tự từ trái sang phải. Giả sử có một viên bi tại ô (y, x) - dòng y cột x, bi có thể di chuyển đến 1 trong 4 ô (y+1, x), (y-1, x), (y, x+1), (y, x-1), nếu ô đó đang trống. Cho vị trí bắt đầu và vị trí kết thúc của viên bi, hãy viết chương trình xác định xem có tồn tại đường đi để di chuyển viên bi hay không.

Dữ liệu nhập: gồm các dòng sau

- Dòng thứ nhất gồm năm số nsysxdydx, mỗi số cách nhau một khoảng trắng (2 ≤ n ≤ 9; 1 ≤ sy, sx, dy, dx ≤ n). sy là chỉ số dòng, sx là chỉ số cột của viên bi cần di chuyển. dy là chỉ số dòng, dx là chỉ số cột của vị trí cần di chuyển viên bi đến.

- Trong n dòng tiếp theo, mỗi dòng gồm n số nguyên 0 hoặc 1, mỗi số cách nhau một khoảng trắng, biểu thị tình trạng của trò chơi. Số 1 nghĩa là vị trí ô đó có bi, số 0 nghĩa là vị trí ô đó đang trống.

(Dữ liệu cho bảo đảm tại ô (sysx) có giá trị là 1, tại ô (dydx) có giá trị là 0)

Dữ liệu xuất:

- Nếu tìm được đường đi, in ra YES.

- Nếu không tìm được đường đi, in ra NO.

Ví dụ

  • input
    2 1 1 2 2
    1 0
    1 0
    output
    YES
  • input
    2 1 1 2 2
    1 1
    1 0
    output
    NO
  • input
    3 1 1 3 3
    1 0 1
    1 0 0
    1 1 0
    output
    YES
Back to Top