Airport Limousine

Problem Statement

Airport Limousine Problem Description An airport limousine can take several riders to the airport at the same time, and on the way back to the starting point the driver may pick up more riders for the next trip. A map of the rider locations is given as a matrix mat with mat_rows rows and mat_columns columns. Each cell holds one of: 0 : an empty path cell; 1 : a path cell holding one rider; -1 : an obstruction, which can never be entered. The rules of motion are: The driver starts at cell (0, 0) and the airport is at cell (mat_rows - 1, mat_columns - 1) . On the way to the airport the driver may only move right or down through non-obstructed cells. After reaching the airport the driver returns to (0, 0) moving only left or up through non-obstructed cells. Passing through a cell that holds a rider picks that rider up, and the cell then becomes an empty path cell, so the same rider is never counted twice. If there is no valid route from (0, 0) to the airport, no riders can be collected at