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
3
000
010
000
000
000
000
000
000
000
1 1
-1
Sample Output
26
Comments
The beer can flow in all 6 directions, including upwards.