Robot

Xem PDF

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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\)) và (\(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 ở ô (\(L_1,C_1\)) cần phải di chuyển đến ô (\(L_2,C_2\)). 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ừ ô (\(L_1,C_1\)) tới ô (\(L_2,C_2\))
  2. Số lần đổi hướng ít nhất để robot có thể di chuyển từ ô (\(L_1,C_1\)) tới ô (\(L_2,C_2\)) 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).

Input

  • Dòng thứ nhất chứa số nguyên \(n,(<n< 1000)\); 
  • \(n\) dòng tiếp 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ố \(L_1,C_1, L_2,C_2\) (đảm bảo là các ô (\(L_1,C_1\)) và (\(L_2,C_2\)) là các ô tự do).

Output

  • 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.

Example

Test 1

Input
5
0 1 1 0 0
0 0 0 1 0
1 0 1 1 0
0 0 0 1 0
0 0 0 0 0
1 1 1 5 
Output
4 2 2
Note


Bình luận

Không có bình luận nào.