Laboratory 3
InterviewTime limit0.25sMemory limit512 MB
Given a grid with walls and up to 10 viruses, choose M of them to activate simultaneously and minimize the time until the virus fills every empty cell, or print -1.
- Level
Medium7 of 10
- Topics
- BFS, Backtracking, Brute force, Simulation
- Solved
- No attempts yet
Problem
Seungwon has broken into a laboratory that was studying a virus lethal to humans, and he intends to leak it. The virus has an active state and an inactive state. Initially every virus is inactive, and an active virus replicates simultaneously into all adjacent empty cells in the four directions, taking 1 second. Seungwon wants to change M of the laboratory's viruses to the active state.
The laboratory can be represented as a square of size N×N, divided into 1×1 squares. The laboratory consists of empty cells, walls, and viruses, and a wall fills one whole cell. When an active virus reaches a cell containing an inactive virus, the inactive virus becomes active.
For example, consider a laboratory laid out as below. 0 is an empty cell, 1 is a wall, and 2 is the position of a virus.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2
With M = 3, if the viruses are changed to the active state as below, the virus can be spread to every cell in 6 seconds. Walls are shown as -, inactive viruses as *, active viruses as 0, and empty cells as the time at which the virus spreads to them.
* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *
The way that minimizes the time is shown below, and the virus can be spread to every cell in just 4 seconds.
0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *
Given the state of the laboratory, find the minimum time to spread the virus to every empty cell.
Input
The first line gives the size of the laboratory N (4 ≤ N ≤ 50) and the number of viruses that can be placed M (1 ≤ M ≤ 10).
From the second line, N lines give the state of the laboratory. 0 is an empty cell, 1 is a wall, and 2 is the position of an inactive virus. The number of 2s is a natural number greater than or equal to M and less than or equal to 10.
Output
Print the minimum time at which every empty cell of the laboratory contains a virus. If no placement of viruses can spread the virus to every empty cell, print -1.