Feature #4: Maximum Routers

Description

We have several routers interconnected in a rectangular grid. Each router has an ID, and all router IDs are stored in a 2D array. Any router may forward a packet to any of its neighbors above it, below it, to its right or left, in the array, if the neighbor’s ID is higher than its own. We have an important packet that can be injected into any single router in the network. The goal is to have the packet forwarded to as many routers in the network as possible. No router should receive the packet more than once.

We’ll be provided with an m x n matrix containing the IDs for each router. Our task will be to forward the packet to the maximum number of routers.

Let’s try to understand this better with an illustration:

If the packet is inserted into the router with ID 1, then it is transmitted through the maximum number of routers according to the above-defined criteria. In our case, this is 4.

Solution

From the above example, we can see that, from every cell, we can move in at most four directions: up, down, left, and right. We will choose to move ...