Tránh mìn
Xem dưới dạng PDFTìm số bước đi ít nhất của robot từ vị trí xuất phát (S) đến vị trí đích (D) sao cho robot đừng giẫm trúng mìn.
Ghi chú:
- Khi robot di chuyển từ một ô sang ô liền kề được tính là 1 bước.
- Robot chỉ có thể di chuyển sang ô liền cạnh chứ không thể đi chéo.
Ma trận ví dụ và cách đi của robot:
Input: Gồm nhiều bộ test, mỗi bộ test bắt đầu với 2 số nguyên \(R\) (\(1 \le R \le 1000\)) và \(C\) (\(1 \le C \le 1000\)) cho biết số dòng và số cột của ma trận.
Dòng tiếp theo cho biết số lượng dòng có mìn \(r\) (\(0 \le r \le R\)).
\(r\) dòng tiếp theo mô tả vị trí các trái mìn với định dạng: Số đầu tiên là số thứ tự của dòng , tiếp theo là số lượng trái mìn và số thứ tự những cột có chứa mìn trong dòng đó.
2 dòng cuối của mỗi bộ test lần lượt là là vị trí xuất phát và đích đến của robot.
Input kết thúc với \(R=0\) và \(C=0\).
Lưu ý: Các ô trong ma trận đánh số từ (\(0,0\)) đến (\(R-1,C-1\)). Nếu không có đường đi thì in \(-1\)
Output: Với mỗi bộ test, in ra số bước đi ít nhất để robot có thể đến được đích mà không giẫm trúng mìn.
Input mẫu
10 10
9
0 1 2
1 1 2
2 2 2 9
3 2 1 7
5 3 3 6 9
6 4 0 1 2 7
7 3 0 3 8
8 2 7 9
9 3 2 3 4
0 0
9 9
0 0Output mẫu
18
Nhận xét
Giúp robot tìm đường đi tốt nhất nhưng tôi lại không thể tìm lối đi hoàn hảo cho cuộc đời mình:(((((((((((((((
summon minecraft: -1
:(((((