Battle Ground and Mighty Gun
All submissions for this problem are available.The Purge Planet of the replacement dimension is a planet in which the people purge each other to cleanse the society. Later on it was found out that the bureaucrats have invented this purge festival so that the villagers may kill each other and they may remain rich. Athricia, a resident of that planet with her dedicated friends has decided to go for a battle against the rich folk and asks for Rick and Morty’s help. Morty wants to win the battle at any cost but Athricia and her friends were very low in number. However, Rick gave him a weapon called **mighty gun** which could be used only once during the purge. The rich folks kept a royal guard, an army which was divided into small troops scattered at different locations (which can be contained in an **N x M** battle ground). The mighty gun, once launched on some troop is capable of killing all the soldiers of that troop at a time but cannot harm any royal guard in other troops. Can you help Morty in this task? He seeks your help in finding out the maximum number of soldiers he can kill in one shot of his mighty gun and also the total number of royal guard troops gathered against them so that he can divide Athricia’s friends efficiently (the troop killed by the mighty gun should also be included). Two royal guard soldiers belong to the same troop if they are at adjacent positions in the battle ground. Therefore, any soldier who is not at some boundary of the battle ground can have a maximum of **8** adjacent soldiers. ###Input: First line contains single integer **T**, the number of test cases. First line of each test case contains two space separated integers **N** and **M** (size of the battle ground), followed by **N** lines containing **M** integers 0 or 1 where 0 means an empty space and 1 means a royal guard soldier. ###Output: For every test case, output two space separated integers **X** and **Y** where **X** is the number of royal guard troops and **Y** is the maximum number of soldiers that can be killed by a single shot of the mighty gun. ###Constraints: 1 ≤ T ≤ 10 1 ≤ N,M ≤ 1000 ###Subtasks: - 30 points : 1<=N,M<=100 - 70 points : Original Constraints ###Sample Input: 1 4 6 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 ###Sample Output: 2 4 ###EXPLANATION: In the given test case, there are two enemy troops first having positions **(0,3) and (0,4)** second having positions **(1,0), (1,1), (2,1) and (3,2)**. Therefore, the mighty gun should be shot on the second troop killing all the 4 enemy soldiers.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions