Farmer John đổi một con bò của mình lấy bò mà Farmer Don gọi “The Knight”. Cô nhảy như mã cờ vua: ngang hai ô lên một, hoặc xuống hai ngang một, v.v. Không đáp trên đá hay cây nhưng đi lại tốt trên đồng chia $X$ nhân $Y$ ô ($1 \le X \le 150$; $1 \le Y \le 150$).
“The Knight” cũng thích cỏ khô. Bản đồ cho nơi bắt đầu, cây, bụi, đá và chướng ngại khác cùng kiện cỏ khô; tính số bước nhảy cần. K là bò, * chướng ngại, H cỏ khô. Bản đồ mẫu:
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . H
5 | * . . . . . . . . .
4 | . . . * . . . * . .
3 | . K . . . . . . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
1
0 1 2 3 4 5 6 7 8 9 0Đường A, B, C, v.v. tới cỏ trong 5 bước (có thể còn đường khác dài 5):
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . F<
5 | * . B . . . . . . .
4 | . . . * C . . * E .
3 | .>A . . . . D . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
1
0 1 2 3 4 5 6 7 8 9 0Gợi ý: có lẽ dễ nhất dùng hàng đợi vào trước ra trước đơn giản bằng vài mảng song song.
Dữ liệu vào
- Dòng 1: hai số nguyên $X$, $Y$ cách bởi khoảng trắng.
- Dòng $2..Y+1$: dòng $Y-i+2$ có $X$ ký tự không khoảng trắng cho hàng $i$ bản đồ (đọc theo hình trên).
Dữ liệu ra
- Dòng 1: số nguyên là số bước nhảy ít nhất tới cỏ. Luôn đến được.
Ví dụ
Dữ liệu vào 1
10 11 .......... ....*..... .......... ...*.*.... .......*.. ..*..*...H *......... ...*...*.. .K........ ...*.....* ..*....*..
Dữ liệu ra 1
5
Tác giả bài toán: Rob Kolstad, 2009