Woburn Challenge 2001 - Suicidal
It is a well-known fact that all engineers like beer. Not so well-known
however, is that one of the qualifying tests to get the engineering ring
is to be able to estimate the amount of beer in a bowl. This important
skill is absolutely essential to determine how long a lunch break is
needed.
Now, Waterloo is a proud institution, and it would cast a real shadow on
their program if one of their graduates failed to get his/her ring
because of failure in the beer-estimation test (who can forget the great
debacle of
). So, the orientation leaders have decided this year to
preempt such an embarrassment from happening by running a
beer-estimation test during orientation week. Only those who can
successfully pass the test will be allowed to continue in the program
and make their millions at Silicon Valley (now do you get the title?).
Nothing is ever easy at Waterloo and so the beer bowl is a cubic bowl of
dimensions
. Some objects have been placed in the bowl that
take up volume in the bowl (these objects may or may not be floating,
but they will be fully submerged). The pouring of the beer will also be
done at a specified coordinate at the top of the bowl. Each student is
required to determine the maximum volume of beer, which can be
accommodated from the given pouring location and pour that amount into
the bowl. Any overfilling of the bowl will result in failure of the test
and inevitable poverty in life. Note that beer does not flow diagonally
between objects in the bowl.
Input Specification
Each case begins with a single integer
.
The next
lines will represent
cross-sections, from top to bottom
(the walls of the bowl will NOT be included in the input). A 1
indicates a block, a 0
indicates empty space.
Finally, there will be two integers,
and
(the one-based
coordinates where juice is poured at the top). Each layer (2D array) is
separated by a blank line.
There will be multiple test cases; keep reading until
.
Output Specification
The maximum volume of beer that can be poured into the bowl from the
given pouring coordinates.
Sample Input
Copy
3
000
010
000
000
000
000
000
000
000
1 1
-1
Sample Output
Copy
26
Comments
The beer can flow in all 6 directions, including upwards.