Magic Leak Detection

Due: $11$:$59$pm on September $21$st$,2024$

Objectives

$$ Give additional practice with nested loops in C$.$

$$ Give additional practice with dynamic memory allocation and management in C$.$

$$ Give practice with queues in C$.$

Story

Oracles are a mystical entity that can glimpse the future, but sadly, due to the burden of seeing

the ever changing future, they have difficulty conveying the future they see to others. Recently an

oracle at the school has informed you that one part of your most recent inscription is going to fail,

which is about the worst news you could get as magic resource archmage.

You have checked several parts of your inscription, and none are of a concern. You fear that

you might have little time before your inscription goes supernova, so you will check only the most

critical parts so that in the worst case you only lose a tree or two rather than the whole forest in

whatever magic calamity befalls the forest due to this mishap. To aid in your quest to find the

worst possible mistake we refer to the following basics of inscription making,

$$ Inscriptions are composed of free and closed points of a $2$ dimensional grid. $($our current

inscription is Euclidean, which makes our life easier$)$

$$ Magic can directly flow between $2$ adjacent $($in one of the $4$ cardinal directions, i$.$e$.$ up$,$ down,

left, or right$)$ free points.

$$ Magic can indirectly flow between $2$ free points if their is a chain of adjacent free points that

connect them.

$$ If magic directly flows between $2$ points, then it also indirectly flows between them as

well.

$$ Magic will always indirectly flow from a free point to itself.

$$ Magic generated$/$consumed by the inscription is equal to the number of pairs of free points

that can allow for magic to indirectly flow between them.

$$ Pairs are counted only once flowing from x to y is the same as flowing from y to x$.$

We will denote closed points using $$#$$ and free points using $..$ Consider the following inscrip$-$

tion.

$1$

#####

#$...$#

#####

#$..$##

#####

Label the free points with integers starting from $1$ going from top to bottom and left to right.

$$ The free point $1$ can reach $1,2,$ and $3.(3$ pairs$)$

$$ The free point $2$ can reach $2$ and $3.(2$ pairs$)$

$$ The free point $3$ can reach $3.(1$ pair$)$

$$ The free point $4$ can reach $4$ and $5.(2$ pairs$)$

$$ The free point $5$ can reach $5.(1$ pair$)$

The $9$ total pairs implies that the given inscription has a total of $9$ magic generation$/$consump$-$

tion.

A closed point that fails behaves like a free point. If a single closed point fails in the above in$-$

scription, there are multiple possible resulting inscription. Below is one possible way the inscription

can could have a free point fail.

#####

#$...$#

###$.$#

#$..$##

#####

In the failing inscription above there are $13$ total magic generation$/$consumption$.$ In general,

the more magic generated$/$consumed the worse the outcome of the failure. A worse outcome would

be the following inscription,

#####

#$...$#

##$.$##

#$..$##

#####

The above inscription generates$/$consumes $21$ magic.

The exterior of the inscription, and potentially some of the internal closed points, have been

checked for failures, but the failure has not been found. It would be nice to know the magic

generated in the worst possible single failure.

Problem

Please write a program that takes in an inscription description with the locations of possible points

of failure and returns the maximum magic generated by a single failure at a possible point