Nội dung Bài tập
- Mã:
- LINE
- Tên:
- Trò chơi Line
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 64 MB
- Được tạo bởi:
- HCMUP1
Trò chơi Line
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ố n, sy, sx, dy, dx, 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 ô (sy, sx) có giá trị là 1, tại ô (dy, dx) 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.
lưu ý: nhập xuất file với file input là "LINE.inp" và file output là "LINE.out"
Ví dụ:
input
3 1 1 3 3
1 0 1
1 0 1
1 1 0
output
NO
input
3 1 1 3 3
1 0 1
1 0 0
1 1 0
output
YES
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
THPT_NK_DEQUY
#include <iostream>using namespace std;int main(){ cout << "Co ga...