FastPrep

Description

Solutions

Airport Limousine (Maximum Passengers Collected) (Also for Core/Database Intern :)

🤘 INTERN📚RELATED PROBLEMS

A taxi can take multiple passengers to the railway station at the same time. On the way back to the starting point, the taxi driver may pick up additional passengers for his next trip to the airport. A map of passenger location has been created, represented as a square matrix.

The matrix is filled with cells, and each cell will have an integer value as follows:

A value >= 0 represents a path.

A value == 1 represents a passenger.

A value == -1 represents an obstruction.

The rules of motion of taxi are as follows:

The Taxi driver starts at (0,0) and the railway station is at (n-1,n-1). Movement towards the railway station is right or down, through valid path cells.

After reaching (n-1,n-1) the taxi driver travels back to (0,0) by travelling left or up through valid path cells.

When passing through a path cell containing a passenger, the passenger is picked up. Once the rider is picked up the cell becomes an empty path cell.

If there is no valid path between (0,0) and (n-1,n-1) then no passenger can be picked.

The goal is to collect as many passengers as possible so that the driver can maximize his earnings.

For example, consider the following grid:

Start at the top left corner. Move right one, collecting a rider. move down one to the airport. Cell (1, 0) is blocked, so the return path is the reversed of the path to the airport. All paths have been explored, and 1 rider was collected.

Returns

int: maximum number of passengers that can be collected.

🌿 𖡼𖤣𖥧𖡼𓋼𖤣𖥧𓋼𓍊, Credit to robotᥫ᭡.🌿

Example 1:

Input:  mat = [[0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Output: 2 
Explanation:
The driver can contain a maximum of 2 passengers by taking the following path:

(0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (2,3) -> (3,3) -> (3,2) -> (3,1) -> (3,0) -> (2,0) -> (1,0) -> (0,0)

Example 2:

Input:  mat = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]
Output: 5 
Explanation:
The driver can contain a maximum of 5 passengers by taking the following path:
      
(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0)

Constraints:

1 <= n <= 100

-1 <= mat[i][j] <= 1