Kitchen

This problem was used in the following GFU competitions:

• GFU 2024 D3 Q9

You have finally been allowed back into the kitchen for dinner service. But oh no! There are a lot of obstacles between you and your station, and you need to make sure you can get there. You will be given a map of the kitchen, and you need to determine if you can get to your station, or if you should just not show up to dinner service. The map will be made up of the following ASCII characters:

• ‘#’ – walls and/or stoves, basically immovable objects.

• ‘.’ – empty spaces that you can walk through.

• ‘G’ – Chef Ramsey Gordon, who you need to stay at least 2 spaces away from, as he will fire you if you get too close.

• ‘O’ – denotes your station that you need to get to.

• ‘S’ – denotes the starting point of the map, where you start your journey.

The first input will be a single integer n that represents the number of data sets that follow. Each data set will start with 2 integers, r and c, denoting the number of rows and columns in the map of the kitchen, respectively. The next r lines, will consist of c characters each, denoting the map of the kitchen. There is not guaranteed to be an ‘O’ or an ‘S’, and there can be any number of ‘G’ chars. (The Chef can be multiple places at once)

If you can get to your station, output "Very good chef.", if not, output "Don't bother showing up.".

1. Simplified shortest path problem