[Solution] Parcels Kick Start Solution

[Solution] Parcels Kick Start Solution

You have been hired recently as the Chief Decision Maker (CDM) at a famous parcel delivery company, congratulations! Customers love speedy deliveries of their parcels and you have decided to decrease the time it takes to deliver parcels around the world to win customers. You have introduced this idea to the authorities and they have allocated you enough budget to build at most one new delivery office.

The world can be divided into an R×C$\mathbf{R}\times \mathbf{C}$ grid of squares. Each square either contains a delivery office or is empty. You may pick a grid square that does not already contain a delivery office and build a new delivery office there.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The delivery time of a parcel to a square is 0$0$ if that square contains a delivery office. Otherwise, it is defined as the minimum Manhattan distance between that square and any other square containing a delivery office. The overall delivery time is the maximum of delivery times of all the squares. What is the minimum overall delivery time you can obtain by building at most one new delivery office?

Note: The Manhattan distance between two squares (r1,c1)$(r_1,c_1)$ and (r2,c2)$(r_2,c_2)$ is defined as |r1−r2|+|c1−c2|$|r_1-r_2|+|c_1-c_2|$, where |x|$|x|$ denotes the absolute value of x$x$.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow. The first line of each test case contains the number of rows R$R$ and number of columns C$C$ of the grid. Each of the next R$R$

Sherlock and Parentheses Kick Start Solution

Building Palindromes Kick Start Solution

Irregular Expressions Kick Start Solution

Parcels Kick Start Solution

 lines contains a string of C$C$ characters, where each character is either 0$0$ or 1$1$. 0$0$ denotes the absence of a delivery office and 1$1$ denotes the presence of a delivery office in that square.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the minimum overall delivery time you can obtain after adding at most one additional delivery office.

Limits

Time limit: 15 seconds.
Memory limit: 1 GB.

1≤T≤100$1\le \mathbf{T}\le 100$.
There is at least one delivery office in the initial grid.

Test Set 1

1≤R≤10$1\le \mathbf{R}\le 10$.
1≤C≤10$1\le \mathbf{C}\le 10$.

Test Set 2

1≤R≤250$1\le \mathbf{R}\le 250$.
1≤C≤250$1\le \mathbf{C}\le 250$.