Đàn mèo đang được thả rông trong thành phố, người ta chia thành phố thành các hình vuông nhỏ và biết rằng khi đi qua hình vuông đó con mèo sẽ đi tiếp một trong 4 hướng đông, tây, nam, bắc. Hãy in ra số lượng cạm bẫy ít nhất để bắt toàn bộ số mèo.
Giải thuật:
Dùng BFS tại từng ô hãy thêm vào Queue những ô sau:
- Giả sử đang tại ô i.j sẽ có 4 ô xung quanh là (i+1,j), (i-1, j), (i, j+1), (i, j-1), kiểm tra 4 ô này xem ô tiếp theo của nó có phải là ô i,j hay k? nếu có hãy đánh dấu đã visit và thêm vào Queue.
- Tại ô i,j ta sẽ thêm ô tiếp theo của ô i,j vào Queue. ví dụ nếu đang ở ô i,j và i,j có giá trị 'S' (Hướng nam) thì hãy thêm ô tiếp theo là i+1, j vào Queue.
Chú ý: Chỉ thêm những ô chưa được visit.
Giải thuật:
Dùng BFS tại từng ô hãy thêm vào Queue những ô sau:
- Giả sử đang tại ô i.j sẽ có 4 ô xung quanh là (i+1,j), (i-1, j), (i, j+1), (i, j-1), kiểm tra 4 ô này xem ô tiếp theo của nó có phải là ô i,j hay k? nếu có hãy đánh dấu đã visit và thêm vào Queue.
- Tại ô i,j ta sẽ thêm ô tiếp theo của ô i,j vào Queue. ví dụ nếu đang ở ô i,j và i,j có giá trị 'S' (Hướng nam) thì hãy thêm ô tiếp theo là i+1, j vào Queue.
Chú ý: Chỉ thêm những ô chưa được visit.
Solution C++4.3.2