Please and thank you! How to solve this question? (C++)

See more:

C++

Hello pros, I met into this question during daily practice:

Quote:

The Trouble with Celebrity Z

Description
Celebrity Z is very low profile. Z and Y are concentrating on their dinner. They were just getting the latest news that some paparazzi teams are swarming here.
Little Z really doesn't understand how these people are so hungry for gossip nowadays, but today, Little Z really doesn't want to give up his delicious meal, so he can only stay as long as possible to eat, and he hopes to eat as long as possible without being caught by the paparazzi.
The city where Little Z eats can be viewed as a square lattice with N rows and N columns, and each lattice is of type a(i,j) with the following cases:
1. T, indicating that this lattice is a private residential building
2. G, indicating that this grid is an empty lot
3. M, which means that this lattice is the place where little Z is eating, but of course it can also be seen as a vacant lot or a public (non-private) building
4. D, denotes that this square is Z's home.
5. H, which means that this cell is a paparazzi's den.
We consider two grids to be adjacent if they have the same edges, i.e., the top, bottom, left, and right grids are adjacent.
Whenever Little Z and the paparazzi walk, they will only walk on adjacent squares, and neither of them will break into other people's private buildings. Little Z takes at most S steps per second, and since Little Z has a professional race car driver, Little W, as a special driver, the value of S can be very large.
The paparazzi are in their dens when Little Z learns of their arrival. As time passes, every second a number of events occur in the following order:

1. if Little Z is still at the eating spot, then he can choose to eat now this second, or start running away
* If it is to continue eating, then Little Z will not move in this second, and if it is to run away, then Little Z can move no more than S steps around the city in the next few seconds. Once it leaves, Little Z will keep running away without stopping. If it meets a paparazzo at a certain location, then Little Z will be captured.

2. When Z chooses to continue eating or move, all paparazzi will move one step further around the grid, and once the paparazzi have reached a grid, a paparazzo will be sent to stay there. At the very beginning, the paparazzi occupy the grid where all the paparazzi dens are located.
* For example, if Little Z chooses to stay where he is in the 1st second, the paparazzi will spread out in all directions in the 1st second, and if they come across Little Z, Little Z will be caught in the picture
* If small Z starts at (1,1), S is 2, and chooses to move in the 1st second, then small Z can move to the (1,2),(1,3) lattice in the 1st second. Assuming that the paparazzi can come to the (1,2) lattice in the 1st second, then small Z can also pass through the (1,2) lattice at that time, because the paparazzi spreads after small Z chooses to stay or move, and small Z can go to (1,3) lattice by the end of the 1st second. at the end of 1 second, and will not encounter the paparazzi; if the paparazzi can come to the (1,3) lattice at the end of 1 second, then Little Z cannot go to the ((1,3) lattice.
* In other words, the paparazzi always diffuse after Little Z decides whether to stay or move, and Little Z is in a position every second that, if it is not home, ensures that the paparazzi cannot be in that position this second.
Neither the paparazzi nor Little Z can go beyond the edge of the city, and the paparazzi cannot take over Little Z's home. Now Little Z wants to know what is the maximum amount of time he can continue to eat if he has to be able to return home safely.

"Some Kind Hints from the Problem Solver
1. Neither Little Z nor the paparazzi can walk to the T-grid of the map, but they can both walk to the M-grid. 2.
2. Read the question carefully, following the example.


Input format
The first line contains two integers, N and S, which represent the size of the city and the maximum distance that Little Z can move per second.
The next N rows are each composed of N characters, where a(i,j) denotes the specific situation of the jth column of the i-th row. a(i,j) is one of the 5 kinds of characters T, G, M, D, and H. See the title for the meaning of a(i,j).

Output format
One integer in a row, indicating how long Z can continue to eat at most.
If it is impossible for Z to return home, then output -1.

Sample #1
Input #1
7 3
TTTTTTTTT
TGGGGGGT
TGGGGGGT
MGGGGGGD
TGGGGGT
TGGGGGGT
TGHHGGGT

Sample Output #1
2

Hints - 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]
For 30% of the data, S=1.
For 50% of the data, N≤60
For 100% of the data 1≤N≤800,1≤S≤1000, and ensure that a(i,j) in the map has one and only one M, one D, and at least one H. Similarly, ensure that there must be a path that can go from G to M.

What I have tried:

I really tried but don't know how to solve it.

I've tried BFS, but since I'm a beginner I don't really know how to right correct BFS, and I'm also not sure whether or not it is a correct thought.