Library and Archives Canada recently decided to install an alarm system to safeguard the English essays of past generations, and they've hired you to help them.
The Archives may be represented by an matrix, with a cell containing 1
representing an empty room, and 0
representing a wall. Your task is to place exactly alarms in the building so that the essays are maximally safeguarded. Each alarm has a square range of units around its radius, and you're interested in covering a maximum number of rooms.
There are a couple of restrictions:
- no alarm may be placed in a wall
- you may only place one alarm per column or row
- an alarm's range cannot overlap with the outside of the building
- alarm ranges can overlap
Knowing this, what is the maximum number of rooms you can hope to secure?
Input Specification
The first line of input will contain the integer .
The next lines will each contain space-separated integers, representing one row of the Archives.
The next line of input will contain the integer .
The final line of input will contain space-separated integers, with the -th integer denoting .
Output Specification
A single integer; the maximum number of rooms that may be covered by alarms.
Sample Input
4
0 1 1 0
0 1 1 1
1 1 1 1
1 1 1 0
4
1 2 1 1
Sample Output
10
Explanation
You can place the radius alarm at , and two radius alarms at and for a coverage of . You are left with one more alarm, but you cannot cover any more rooms without placing multiple alarms on the same row or column.
Comments
Clarification
The problem statement states that you need to place exactly alarms; along with the row/column restriction, isn't it possible for certain test cases to be impossible to fulfill? Such as any test case with , or less rooms than alarms.
Edit: Nevermind, I didn't see Xyene's reply to the earlier comment.
What does it mean exactly by
For example, a square range of radius 2 covers
"You can place the radius 2 alarm at (1,2), and two radius 1 alarms at (1,0) and (3,1) for a coverage of 10"
doesn't this break the rule about alarms sharing a row or column: (1,2) vs. (1,0).
(it's also a bit unclear which cell is meant by "(1, 2)")
also, given "Your task is to place exactly A alarms in the building"; sometimes the restrictions make this impossible. Is the answer 0 in that case or are we allowed to use fewer than A alarms (it seems to me that placing 4 alarms while obeying restrictions in the example makes it impossible to cover 10 rooms).
Apologies; while the sample input is not wrong, the explanation does include a typo: the alarm should be placed at (indexing from top left, from 0) rather than . The final alarm may be placed at (a solution always exists).
Thanks, makes sense now. I was thinking of the origin at bottom-left (and had a minor bug in my program which was returning 9 at the time).
what does it mean:
Does it mean the alarm range cannot include wall or go outside the n*n squre?
Thx
It cannot go outside the area. For example, in
you may only place an alarm with in the center.