Car

This problem was used in the following GFU competitions:

• GFU 2024 D2 Q4

You have bought a new car, but you are struggling to get it out of the lot. Quick, write a program to plot a path out of the lot before it closes and you're trapped inside with the car salesmen

There will be an integer n denoting the number of test cases to follow. Each test case will begin with 3 space-separated integers on a line, r, c, and s, denoting the number of rows and columns in the lot, and the amount of time (in seconds) you have left until the lot closes. Each of the following r rows will contain c characters denoting the layout of the lot. The characters will be as follows:

• '#' – denotes a concrete block than cannot be passed over.

• '_' – denotes one of those concrete stoppers between the spaces, these take 2 seconds to pass over.

• '.' – denotes and empty space that takes 1 second to pass over.

• '0' – denotes a car that cannot be passed over.

• '=' – denotes the exit gate from the lot, it will always be on the edge.

• '@' – denotes the location of your car in the lot.

You can only move in 4 directions, up, down, left, and right.

For each data set, if you make it out of the lot in time for closing, output the string "Just in Time-berlake" followed by a space and the number of seconds remaining in your time. If you do not, output the string "It's gonna be me". If you make it out in a number of steps equal to the amount of time left, you do in fact make it out (printing a 0 is permissible).

1. Depth-First Search (DFS) or Breadth First Search (BFS)

• DFS -> Stack based

• BFS -> Queue based