Problem · Matrix

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

● HardSnowflakeINTERNOA

Problem statement

A taxi travels through a square matrix from (0, 0) to the railway station at (n - 1, n - 1), then returns to (0, 0).

Each cell has one of the following values:

0: an empty path cell
1: a path cell containing one passenger
-1: an obstruction that cannot be entered

On the outward trip, the taxi may move right or down. On the return trip, it may move left or up. Whenever the taxi enters a cell containing a passenger, that passenger is collected and the cell becomes empty.

If no valid route exists between the endpoints, no passenger can be collected. Otherwise, maximize the number of distinct passengers collected over the outward and return trips.

Complete maximumPassengersCollected with int mat[n][n].

Returns: int, the maximum number of passengers that can be collected.

Function

maximumPassengersCollected(mat: int[][]) → int

Examples

Example 1

mat = [[0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]return = 2

The taxi can collect both passengers by taking the outward route along the top row and right edge, then returning along the bottom row and left edge. The maximum is 2.

Example 2

mat = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]return = 5

A legal round trip is (0,0) → (0,1) → (1,1) → (2,1) → (2,2) → (2,1) → (2,0) → (1,0) → (0,0). It avoids both obstruction cells and collects all five passengers, so the answer is 5.

Constraints

1 <= n <= 100

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