All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
You are given a rectangular grid with N rows and M columns. Each its cell is either empty, contains an enemy, or contains a laser.
The lasers are capable of shooting. Each one 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.
Find out whether it's possible to kill all the enemies on the grid. If it's possible, output "Possible", otherwise output "Impossible".
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains the pair of integers N and M denoting the size of the grid.
The next N lines contain M characters each. The characters can be one of the following ones:
- '.' denoting an empty cell.
- 'E' denoting an enemy.
- 'L' denoting a laser.
For each test case, output a single line containing the answer to the corresponing test case.
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 50
- The number of lasers will be between 1 and 16, inclusive.
Input: 3 2 2 E. L. 2 4 E.EL LL.. 3 3 EE. L.L L.. Output: Possible Possible Impossible
|Tags||bruteforce, cook49, greedy, simple, witua|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.