Xin vui lòng và cảm ơn bạn! Làm thế nào để giải quyết câu hỏi này? (C++)

Xin chào các chuyên gia, tôi đã gặp câu hỏi này trong quá trình luyện tập hàng ngày:

Trích dẫn:

Rắc rối với người nổi tiếng Z
Sự miêu tả
Người nổi tiếng Z có cấu hình rất thấp. Z và Y đang tập trung vào bữa tối của họ. Họ vừa nhận được tin tức mới nhất rằng một số đội săn ảnh đang tụ tập ở đây.
Tiểu Z thực sự không hiểu dạo này những người này sao lại thèm tin đồn, nhưng hôm nay Tiểu Z thật sự không muốn bỏ bữa ăn ngon lành của mình nên chỉ có thể ở lại càng lâu càng tốt để ăn, và cậu ấy hy vọng có thể bỏ qua bữa ăn ngon lành của mình. ăn càng lâu càng tốt mà không bị tay săn ảnh bắt gặp.
Thành phố nơi bé Z ăn uống có thể xem như một ô vuông có N hàng và N cột, mỗi ô thuộc loại a(i,j) với các trường hợp sau:
1. T, chỉ ra rằng mạng lưới này là một tòa nhà dân cư tư nhân
2. G, biểu thị lưới này là lô đất trống
3. M, nghĩa là cái lưới này là nơi bé Z đang ăn uống, nhưng tất nhiên cũng có thể coi đó là bãi đất trống hoặc tòa nhà công cộng (không riêng tư)
4. D, biểu thị hình vuông này là nhà của Z.
5. H, nghĩa là phòng giam này là hang ổ của các tay săn ảnh.
Chúng ta coi hai lưới là liền kề nếu chúng có cùng các cạnh, tức là các lưới trên, dưới, trái và phải liền kề nhau.
Mỗi khi Tiểu Z và các tay săn ảnh đi dạo, họ sẽ chỉ đi trên các quảng trường liền kề, và cả hai đều không đột nhập vào nhà riêng của người khác. Little Z thực hiện tối đa S bước mỗi giây, và vì Little Z có một tay đua xe chuyên nghiệp, Little W, là tay đua đặc biệt nên giá trị của S có thể rất lớn.
Các tay săn ảnh đang ở trong hang của họ khi Little Z biết được sự xuất hiện của họ. Khi thời gian trôi qua, cứ mỗi giây lại có một số sự kiện xảy ra theo thứ tự sau:
1. Nếu Tiểu Z vẫn còn ở chỗ ăn, thì cậu ấy có thể chọn ăn ngay bây giờ hoặc bắt đầu bỏ chạy
* Nếu là tiếp tục ăn thì Tiểu Z sẽ không di chuyển trong giây phút này, còn nếu định bỏ chạy thì Tiểu Z không thể di chuyển quá S bước quanh thành phố trong vài giây tiếp theo. Một khi nó rời đi, Tiểu Z sẽ tiếp tục chạy trốn không ngừng. Nếu gặp paparazzo ở một địa điểm nhất định thì Little Z sẽ bị bắt. 2.
2. Khi Z chọn tiếp tục ăn hoặc di chuyển, tất cả các tay săn ảnh sẽ di chuyển thêm một bước nữa quanh lưới và khi các tay săn ảnh đã đến được lưới, một tay săn ảnh sẽ được cử đến ở lại đó. Ngay từ đầu, các tay săn ảnh đã chiếm giữ mạng lưới nơi đặt tất cả các tụ điểm của các tay săn ảnh.
* Ví dụ: nếu Little Z chọn giữ nguyên vị trí của mình trong giây đầu tiên, các tay săn ảnh sẽ tản ra mọi hướng trong giây đầu tiên và nếu họ bắt gặp Little Z, Little Z sẽ bị bắt gặp trong ảnh
* Nếu Z nhỏ bắt đầu tại (1,1), S là 2 và chọn di chuyển trong giây đầu tiên thì Z nhỏ có thể di chuyển đến mạng (1,2),(1,3) trong giây đầu tiên. Giả sử các tay săn ảnh có thể đến mạng (1,2) trong 1 giây đầu tiên thì Z nhỏ cũng có thể đi qua mạng (1,2) tại thời điểm đó, vì các tay săn ảnh sẽ lan truyền sau khi Z nhỏ chọn ở lại hoặc di chuyển, và Z nhỏ có thể tiến tới mạng (1,3) vào cuối giây đầu tiên. hết 1 giây sẽ không gặp phải tay săn ảnh; nếu các tay săn ảnh có thể đến được mạng (1,3) sau 1 giây thì Little Z không thể đến được mạng ((1,3).
* Nói cách khác, các tay săn ảnh luôn khuếch tán sau khi Tiểu Z quyết định nên ở lại hay di chuyển, và Tiểu Z luôn ở trong một vị trí mà nếu không phải ở nhà thì đảm bảo rằng các tay săn ảnh không thể ở vị trí đó trong giây phút này.
Cả paparazzi và Little Z đều không thể đi ra ngoài rìa thành phố, và paparazzi cũng không thể chiếm được nhà của Little Z. Bây giờ Little Z muốn biết khoảng thời gian tối đa cậu có thể tiếp tục ăn uống nếu phải trở về nhà an toàn là bao nhiêu.
“Một số gợi ý hay từ Người giải quyết vấn đề
1. Cả Little Z và các tay săn ảnh đều không thể đi đến lưới chữ T của bản đồ, nhưng cả hai đều có thể đi đến lưới chữ M. 2.
2. Đọc kỹ câu hỏi, làm theo ví dụ.

định dạng đầu vào
Dòng đầu tiên chứa hai số nguyên N và S, biểu thị quy mô của thành phố và khoảng cách tối đa mà Little Z có thể di chuyển trong một giây.
N hàng tiếp theo, mỗi hàng gồm có N ký tự, trong đó a(i,j) biểu thị tình huống cụ thể của cột thứ j của hàng thứ i. a(i,j) là một trong 5 loại ký tự T, G, M, D và H. Xem tiêu đề để biết ý nghĩa của a(i,j).

Định dạng đầu ra
Một số nguyên liên tiếp, cho biết Z có thể tiếp tục ăn tối đa trong bao lâu.
Nếu Z không thể trở về nhà thì xuất -1.

Mẫu số 1
Đầu vào mẫu số 1
7 3
TTTTTTTTT
TGGGGGGT
TGGGGGGT
MGGGGGGD
TGGGGGT
TGGGGGGT
TGHHGGGT

Đầu ra mẫu số 1
2

gợi ý
[Sample Explanation
For the sample, a possible approach is to stay for two seconds.
1. then take three steps to (3,3) at the third second
2. at the 4th second, take three steps to (3,6)
3. take two steps to (4,7) in the 5th second without encountering paparazzi.

[Data Range]

Đối với 30% dữ liệu, S=1.
Đối với 50% dữ liệu, N<60
Đối với 100% dữ liệu 1

Và tôi thực sự đã cố gắng nhưng không biết làm thế nào để giải quyết nó.

Những gì tôi đã thử:

Tôi đã thử BFS, nhưng vì là người mới bắt đầu nên tôi thực sự không biết cách sửa BFS cho đúng và tôi cũng không chắc liệu đó có phải là một suy nghĩ đúng hay không.