Pre-requisites: Bruteforce, Greedy
Given a rectangular grid with N rows and M columns. Each its cell is either empty, contains an enemy, or contains a laser. Each laser can shoot in one of three directions: either left, right or up. When a laser shoots at some direction, it kills all the enemies on its way. There’re L lasers on the grid.
You are to determine whether it’s possible to kill all the enemies on the grid.
The key observations are that there’re at most 16 lasers on the grid and there’re only 3 directions to shoot.
So, let’s just choose those lasers, who will shoot in the up direction(let’s call them “vertical” lasers, those who are not chosen are “horizontal”) There’re at most 216 variants, so we can simply iterate through them. After that, we can solve the problem independently for each row. How?
If there’re no alive enimies left on a row(after the “vertical” lasers shot), then it’s OK. Otherwise, if there’re no “horizontal” laser in the row, then the current variant fails. If there’re one “horizontal” laser on the row, then we should check if all the enemies lies to the one side of the laser. If there’re one “horizontal” laser on the row, then it’s OK anyway(we can make the most left one shoot to the right, the most right one shoot to the left - so all the row will be covered).
Total complexity is O( 2L NM ) per testcase.
Please, check out Setter’s and Tester’s solutions for your better understanding.
Setter’s Solution: link
Tester’s Solution: link