Feature #9: Update Configuration

Description

We have a network topology in which several network routers are interconnected in a rectangular grid. A router has four neighboring routers: $up,\ right,\ left,$ and $down$. A router transmits a configuration update control message to its 4 directionally adjacent neighbors in response to a configuration change. The routers exchange control messages with their adjacent neighbors at one-minute intervals.

A router accepts the configuration change only if it receives a configuration update from its four neighbors, mentioned above, and then it updates its configuration.

We will be provided an m * n matrix of integers ranging from 0 to 2. The ranged integers represent the state of the configuration flow:

• 0 represents a router with VLAN ID 0.
• 1 represents a router with VLAN ID 1; it has yet to receive the configuration update.
• 2 represents a router with VLAN ID 2; it has received the transmission and has updated its configuration.

Our task will be to determine the minimum minutes before the configuration changes stop propagating, given that the configuration has been updated in some routers.

We can assume that there are no $isolated\ routers$ (all the routers have at least one router in their neighbors with a VLAN ID greater than zero), and configuration updates will flow to all the routers without failing.

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