Scribd
Upload
35 views2 pages

Maximum Passengers in Taxi Problem

The document outlines a problem where a taxi driver must navigate a square matrix to pick up passengers while adhering to specific movement rules. The goal is to maximize the number of passengers collected during the trip to the railway station and back. Sample inputs and outputs illustrate possible paths and the maximum passengers that can be picked up.

Uploaded by

nageshiatharaju090
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
35 views2 pages

Maximum Passengers in Taxi Problem

The document outlines a problem where a taxi driver must navigate a square matrix to pick up passengers while adhering to specific movement rules. The goal is to maximize the number of passengers collected during the trip to the railway station and back. Sample inputs and outputs illustrate possible paths and the maximum passengers that can be picked up.

Uploaded by

nageshiatharaju090
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

Problem Statement- A taxi can take multiple passengers to the railway station at

the same [Link] 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 initial value as
follows:

A value greater than or equal to zero represents a path.


A value equal to 1 represents a passenger.
A value equal to -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
[Link] 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.

Sample Input 0

0 0 0 1

1 0 0 0

0 0 0 0

0 0 0 0

Sample Output 0

Explanation 0

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)

Sample Input 1

0 1 -1

1 0 -1
1 1 1

Sample Output 1

Explanation 1

The driver can contain a maximum of 5 passengers by taking the following path (0,0)
→ (0,1) → (1,1) → (2,1) → (2,2) → (2,1) → (2,0) → (1,0) → (0,0)

You might also like