Click here to Skip to main content
15,908,673 members
Please Sign up or sign in to vote.
1.00/5 (3 votes)
See more:
Hello pros, I met into this question during daily practice:

The Trouble with Celebrity Z

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

Sample Output #1

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.
Updated 14-Jan-24 2:25am
Richard MacCutchan 13-Jan-24 10:09am    
Andre Oosthuizen 14-Jan-24 5:19am    
Same here - tl:dr

While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

Just copy'n'pasting what looks like your homework assignment and saying "I'm a beginner" isn't going to get you a solution.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
Share this answer
Problem with the example #1
The city in which Little Z eats can be viewed as a square grid with N rows and N columns.

7 3

If you shorten the lines so that there are only 7 fields and leave field D on the right-hand edge and also wait 2 time units, you get following results. (The number of paparazzi is infinite). It is also not mentioned that Little Z has field D as its goal, which I would assume.

After 2 time units:
T T T T T T T  
T G G G G G G 
T G G G G G G 
M G G G G G D 
T G h h h G G  
T h h h h G G  
T h H H h h G

After 3 time units:
T T T T T T T  
T G G G G G G 
T G G G G G G 
T G h M/h G G D 
T h h h h G G 
T h h h h h G 
T h H H h h h

As you can see, he would still make it home after waiting 2 time units. He would only need 2 time units on the direct route and that is enough. He can therefore continue eating for 2 time units.

As a solution, I would suggest gradually filling all fields with h and checking whether there is still a path left. Little Z would need 2 time units on direct route.
Share this answer

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900