Airport Limousine

Problem Statement

Airport Limousine Problem A limousine service for an airport can carry several passengers at once. The driver starts at the top-left corner of an n x n grid, drives to the airport at the bottom-right corner, and then drives back to the top-left corner. On both legs of the trip the driver may pick up passengers. Each cell of the grid holds one of three values: 0 - an empty cell the limousine may drive through 1 - a cell the limousine may drive through, holding one passenger -1 - an obstruction; the limousine can never enter this cell Movement rules: On the outbound leg, from (0, 0) to (n - 1, n - 1) , the limousine may only move right or down . On the return leg, from (n - 1, n - 1) back to (0, 0) , it may only move left or up . Every cell entered on either leg, including (0, 0) and (n - 1, n - 1) , must not be an obstruction. Passing through a cell holding a passenger picks that passenger up, and the cell immediately becomes 0 . A cell therefore contributes at most one passenger to the