--- Day 3: A Strange New Pandemic ---
You flop onto your bed after a long day stuck in the underground bunker and, for a moment, watch dust motes spin in the shaft of late light. Humans feels like a complicated animal: some of us hungry for power and wealth, always fighting, while turning swords into plowshares remains a distant dream.
Patch has already briefed you for your third day working with the elves, so you aren't surprised when she knocks on your door the next morning and leads you up to the office floors. What does surprise you is where she takes you - to the back of the corridor and into a room labeled "Disease Control".
"Okay, please don't tell me covid's coming back," you say, half-expecting the worst.
"Not for humans," Patch answers. "But there's a new virus spreading through farm and pet animals. It can't jump to people, but it's still very bad news."
She taps the electronic whiteboard and brings up sketches. "We have already modelled how the virus behaves. The animals arranged in a rectangular grid, each day the infection spreads from any infected animal to adjacent uninfected hosts in the four cardinal directions. To control it, we can build isolation barriers inside the grid, but building barriers around each infected group takes a whole day."
A serious-looking elf steps forward and introduces himself as Mike, the lead scientist. "We want to minimise the number of animals that become newly infected each day. We are using a simple greedy strategy: every day we will construct barriers around the infected group that currently threatens the largest number of uninfected animals. Your job is to do the cost analysis, as in, how many barriers will we need if we follow this strategy until the outbreak is contained."
Can you help the elves calculate the total number of barriers required to isolate the virus using their greedy approach?
The initial state of the world is modelled as a 2D grid, where each item contains a binary value (0 or 1) meaning whether the animal is infected initially.
A barrier can be installed between any two adjacent (in four directions) animals, on the shared boundary.
Every night, the virus spreads from all infected animals to all neighbouring animals in all four directions, unless blocked by a barrier.
Resource constraints are tight. Each day, you can install barriers around only the most dangerous infected group (i.e., the continuous block, in four directions, of infected animals that threatens the most uninfected animals the following night).
Animals are ranked by their row index followed by their column index, an animal with a higher (row, column) index is perceived to be more important. In case of a tie in the number of threatened uninfected animals, you should save the most important animal you can possibly save.
Your job is to determine the number of barriers used in total, before either the virus is fully contained or all animals are infected.
The input file is in the following format:
M and N, the size of the 2D grid.M lines each contain N integers separated by spaces, each integer is either 0 or 1. This indicates the initial state of the grid. 0 means an animal is initially uninfected, and 1 means it is initially infected.You should output a single integer, giving the total number of barriers used.
Sample Input 1:
4 8
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
Sample Output 1:
10
Explanation 1:
Initially there are two infected groups on the grid.
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
On the first day, the left group endangers 5 uninfected animals, while the right group endangers 4. Therefore, we build barriers around the left group.
0 | 1 | 0 0 0 0 0 1
0 | 1 | 0 0 0 0 0 1
-
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
As seen above, this consumes 5 barriers. Then, the first night, the virus spreads from the right group:
0 | 1 | 0 0 0 0 1 1
0 | 1 | 0 0 0 0 1 1
-
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1
On the second day, we only have one uncontained group left. Therefore, we build barriers around the right group:
0 | 1 | 0 0 0 0 | 1 1
0 | 1 | 0 0 0 0 | 1 1
-
0 0 0 0 0 0 | 1 1
-
0 0 0 0 0 0 0 | 1
This consumes another 5 barriers. Now the virus is fully contained.
Therefore, in total, we used 5 + 5 = 10 barriers.
Sample Input 2:
3 8
0 1 0 0 0 0 0 1
0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 1
Sample Output 2:
16
Explanation 2:
Initially there are three infected groups on the grid.
0 1 0 0 0 0 0 1
0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 1
On the first day, the left group endangers 5 uninfected animals, the middle group endangers 4 uninfected animals, while the right group endangers 3. Therefore, we build barriers around the left group.
0 | 1 | 0 0 0 0 0 1
0 | 1 | 0 1 0 0 0 1
-
0 0 0 0 0 0 0 1
This consumes 5 barriers. Then, the first night, the virus spreads:
0 | 1 | 0 1 0 0 1 1
0 | 1 | 1 1 1 0 1 1
-
0 0 0 1 0 0 1 1
Not counting the contained left group, we have two groups left. The middle group endangers 5 animals while the right group endangers 3. We build barriers around the middle group on day 2:
0 | 1 | 0 | 1 | 0 0 1 1
- -
0 | 1 | 1 1 1 | 0 1 1
- - -
0 0 0 | 1 | 0 0 1 1
This consumes another 9 barriers, note that the existing barrier is not counted again. The virus spreads on the second night:
0 | 1 | 0 | 1 | 0 1 1 1
- -
0 | 1 | 1 1 1 | 1 1 1
- - -
0 0 0 | 1 | 0 1 1 1
Only one group left, so in our third day we install barriers around the right group:
0 | 1 | 0 | 1 | 0 | 1 1 1
- -
0 | 1 | 1 1 1 | 1 1 1
- - -
0 0 0 | 1 | 0 | 1 1 1
This takes another 2 barriers, and now the virus is fully contained.
Therefore, in total, we used 5 + 9 + 2 = 16 barriers.