The goal is to come up with a 100% coverage solution that does not use the trivial brute force approach.
If the response to this challenge is high and serious, I will morph this into a contest and offer prizes (e.g. cash, memberships, maybe some BYOND swag).
You are the leader of a base and in charge of defending it from hordes of zombies. It gets tough though as the base is owned by a major corporation and will only pay you based on financial performance, but you try your best to kill the zombies in an economical fashion. Zc number zombies attack you straight on and at a constant speed, that is, the zombies stay in their initial column and any cluster of zombies in a row stay in the same row. ________Zombie Horde___________ | ZZ | | ZZZ | | ZZZ | Attack | ZZZZZZ | Direction | ZZZZZZ | | | ZZZZZZ | | | | V | | | | | | |______________________________| You You have two weapons at your disposal: one will take out entire rows of zombies as they attack you, the other will take out entire columns of zombies. You only fire the row weapon N number of times. The column weapon is owned by your company and they would like you to fire this weapon as little as possible -- they only reward you when you fire the weapon the minimum possible times. Using the above example, let's say N = 1: ________Zombie Horde___________ | ZZ | @ Row weapon | ZZZ | | ZZZ | Attack | ZZZZZZ | Direction | ZZZZZZ | | | ZZZZZZ | | | | V | | | | | | |______________________________| The row weapon should be fired at the row of zombies in the back so that you only have to fire the column weapon 9 times. Let's say N = 2: ________Zombie Horde___________ | ZZ | | ZZZ | @ Row weapon 1 | ZZZ | @ Row weapon 2 | ZZZZZZ | | ZZZZZZ | | ZZZZZZ | | | | | | | | | |______________________________| The row weapon should be fired at the pair of rows containing three zombies so that you only have to fire the column weapon 8 times. Let's say N = 3: ________Zombie Horde___________ | ZZ | | ZZZ | | ZZZ | | ZZZZZZ | @ Row weapon 1 | ZZZZZZ | @ Row weapon 2 | ZZZZZZ | @ Row weapon 3 | | | | | | | | |______________________________| The row weapon should be fired at the three rows containing six zombies each so that you only have to fire the column weapon 5 times. Problem name: Zombies Input format: * Line 1: A single integer: N * Line 2..Zc+1: Coordinate locations of zombies Sample Input: 3 0 3 0 4 1 6 1 7 1 8 2 6 2 7 2 8 3 14 3 15 3 16 3 17 3 18 3 19 4 14 4 15 4 16 4 17 4 18 4 19 5 14 5 15 5 16 5 17 5 18 5 19 Output Format: * Line 1..N: "Row " & Row coordinate to fire row weapon. * Line N+1: Number of columns to fire column weapon. Sample Output: Row 3 Row 4 Row 5 5 Objectives: * Shortest computation time * Best coverage Notes: There is a very obvious brute force way of minimizing the use of the column weapon. This guarantees maximizing coverage at the great expense of computation.