Problem Statement

Airport Limousine Round Trip A limousine service runs between a city and its airport. The limousine can carry any number of passengers at once, so on a single journey the driver simply picks up everybody standing along the route -- and on the way back from the airport the driver keeps collecting people for the next journey. The city is a square grid of n by n cells given as a matrix matrix , where matrix[i][j] is: 0 -- an empty stretch of road the limousine may drive through, 1 -- a stretch of road with exactly one passenger waiting on it, -1 -- an obstruction the limousine can never drive through. The garage is the cell (0, 0) and the airport is the cell (n - 1, n - 1) . One round trip works like this. Starting at (0, 0) , the driver moves only right or down , one cell at a time, until reaching (n - 1, n - 1) . Every cell entered must be a road cell ( 0 or 1 ). Starting at (n - 1, n - 1) , the driver then moves only left or up , one cell at a time, until reaching (0, 0) again. Again,