Sau một khoảng thời gian nhất định, các robot đang hoạt động tại một căn cứ sẽ đến kiểm tra tại trạm bảo trì của mình. Căn cứ này có thể được xem là một khu vực hình chữ nhật có kích thước ~M \times N~ ô đơn vị; các hàng được đánh số từ trên xuống dưới và từ ~1~ đến ~M~; các cột được đánh số từ trái sang phải và từ ~1~ đến ~N~; giao giữa hàng ~i~ và cột ~j~ là ô ~(i, j)~, mỗi ô có giá trị ~0~ hoặc ~1~. Robot có thể di chuyển theo phương ngang hoặc phương đứng qua lần lượt từng ô, và có thể đi qua bất kì ô nào (kể cả các ô thuộc trạm khác) nếu muốn. Căn cứ này gồm nhiều trạm bảo trì khác nhau, mỗi trạm là một miền gồm tất cả các ô có số ~1~ liền kề nhau (hai trạm khác nhau không có một cạnh ô vuông nào chung). Vị trí hiện tại của robot ~R~ là ô ~(x, y)~ và trạm bảo trì của robot này là trạm duy nhất có diện tích lớn nhất trong căn cứ (diện tích của một trạm là tổng số ô của trạm đó). Để tiết kiệm năng lượng, robot ~R~ cần tìm đường đi ngắn nhất đến trạm của mình, độ dài của đường đi là số lượng các ô mà robot đi qua.
Yêu cầu: Hãy tìm độ dài đường đi ngắn nhất từ vị trí của robot ~R~ đến trạm bảo trì của mình.
Dữ liệu vào
- Dòng thứ nhất chứa bốn số nguyên dương lần lượt là ~M~, ~N~, ~x~, ~y~ ~(1 \leq M, N \leq 100)~;
- Trong ~M~ dòng tiếp theo, mỗi dòng gồm ~N~ chữ số ~0~ hoặc ~1~;
Lưu ý: Các số trên một dòng cách nhau ít nhất một dấu cách.
Kết quả ra
- Xuất ra màn hình một số nguyên duy nhất là độ dài đường đi ngắn nhất cần tìm.
Ví dụ
Dữ liệu vào
6 8 4 4
0 0 0 0 1 1 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 0
0 0 0 1 1 0 1 1
1 0 0 0 0 0 1 0
1 1 0 0 0 0 0 0
Kết quả ra
3
Giải thích
- Căn cứ gồm ~4~ trạm, trong đó trạm mà robot ~R~ cần đến là trạm gồm có ~7~ ô có chứa ô ~(4, 7)~. Robot có thể đi lần lượt qua các ô ~(4, 5)~, ~(4, 6)~, ~(4, 7)~ để đến trạm này.
Comments