Plague $2050$ Problem Description In the year $2050,$ a plague outbreak has impacted a state, spreading rapidly, and becoming increasingly contagious. A team of doctors is on a mission to obtain a crucial herb that is located only in a particular part of the state.

The state is structured as a square grid of size N$,$ consisting of N$$N cities, each occupying an area of $1$ unit and with each city having $8$ neighbouring cities, except for those located along the boundaries of grid. These cities are categorized as either infected or uninfected, represented by $1$ and $0,$ respectively. The plague spreads based on specific conditions given below.

If a city is uninfected and has exactly three neighbouring cities that are infected, the plague will spread to that city, causing it to become infected the following day. Any infected city with two or three neighbouring infected cities will remain infected the following day. Any infected city with less than two neighbouring infected cities will become uninfected the next day, due to reduced transmission of the infection. Any infected city with more than three neighboring infected cities will become uninfected the next day, due to increased medical attention from the government. A team of doctors is working to find a permanent cure for the plague and needs to prepare medicine from an herb that is only available in a specific city.

Each day, the team of doctors faces two options: they can either stay in their current city or move to an adjacent city $($connected above, below, left, or right$).$ As the plague spreads, they receive daily reports on the status of infected and non$-$infected cities, allowing them to predict the conditions for the following day. They plan to travel to cities that will be uninfected the next day and avoid staying in cities that are expected to become infected.

Given the doctor's team's starting city represented as $"$s$,"$ the city where the herb can be found as $"$d$,"$ and today's report on city statuses, assist them in determining the minimum number of days required to reach the city with the herb if they move optimally. They can travel to only one city in one day.