ROBOT10 - Robot
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Cho lưới ô vuông kích thước n dòng và n cột. Các dòng của lưới được đánh số từ 1 đến n.  Các cột của lưới cũng được đánh số từ 1 đến n. Ô nằm trên giao của dòng i và cột j của lưới được gọi là ô (i,j)(i,j) được gọi là tọa độ của nó. Mỗi ô của lưới chứa một số thuộc tập {0, 1}. Ô chứa số 0 được gọi là ô tự do còn ô chứa số 1 được gọi là ô bị cản. Robot được đặt ở ô (L1, C1) cần phải di chuyển đến ô (L2, C2). Robot chỉ có thể di chuyển theo hướng thẳng đứng hoặc hướng nằm ngang.

Yêu cầu: Cần xác định:

1) Số lần đổi hướng ít nhất để robot có thể di chuyển từ ô (L1, C1) tới ô (L2, C2).
2) Số lần đổi hướng ít nhất để robot có thể di chuyển từ ô (L1, C1) tới ô (L2, C2) trong tình huống được phép biến một ô bị cản thành ô tự do.
3) Số lượng các ô bị cản mà việc loại bỏ bất cứ một ô nào trong số chúng, ta đều đạt được số lần đổi hướng như trong câu 2).

Dữ liệu 

- Dòng thứ nhất chứa số nguyên n, 1<=n<=1000;
- n dòng tiếp theo, mỗi dòng chứa n số 0 hoặc 1 được ghi cách nhau bởi dấu cách mô tả trạng thái của lưới
- Dòng thứ n+2 chứa 4 số L1, C1,L2, C2 (đảm bảo là các ô (L1, C1) và ô (L2, C2là các ô tự do).

Kết quả:

Ghi ra ba số nguyên là các câu trả lời cho 3 yêu cầu tương ứng nêu trong đầu bài

Ví dụ


Nguồn: NĐN 20172018

Back to Top