ADASEA  Ada and Island
Ada the Ladybug just read a book from famous author Dobsonfly Daffoedil. It is about Robinson's Cicada, who was flying over sea. Suddenly she had an accident and fell to island below her. Luckily the island was big enough, so she could recover and fly home till Friday night... or something like that.
As Ada was reading through the book, she fell asleep and started dreaming. She was thinking about how lucky the Cicada was, that she fell into such big island. She could have fallen into a smaller one or even to sea.
It keeps bugging her, so she has asked you to tell her the expected size of island, the Cicada will fall to (considering equal probability for all coordinates). Since Ada is not friend of floating point numbers, she wants the answer in some "nice" form.
Island is considered to be union of any '#' characters, which share side.
Input
The first line contains an integer T, the number of testcases.
Each testcase begins with two integers N, M, 1 ≤ N, M ≤ 1000
Afterward N lines follow, with M characters. Each of the characters is either '#' (island) or '~' (sea).
Output
For each testcase print the expected size of sea. Output it as p / q, where p and q has no common divisor. If p / q can be printed as an integer (not as fraction), do so!
Example Input
5 3 4 ~~~~ ~~~~ ~~~~ 3 3 #~~ ##~ ~~~ 4 5 #~##~ #~~~# ~~~~# ####~ 1 1 # 4 4 ~~~~ ##~~ ~##~ ##~~
Example Output
0 1 7 / 5 1 9 / 4
hide comments
nadstratosfer:
20180204 22:13:20
Too big for Python. Through some antiprogramming I've managed to push my solution past a few more testfiles but my best effort needs over 4.5s on Ideone for a worstcase file. I guess unless Python 4 comes out one day with Cstyle arrays, there's no fun to be had with big graphs here :(


kaushalag29:
20180204 10:01:13
@morass: are there spaces between numbers and slash?


roberttz:
20171229 12:40:47
Don't forget to use long long 

morass:
20170405 21:51:03
@anonymous: Well: Maximum number of testcases is "200" and maximum sum of "N*M" is 9498720 

anonymous:
20170403 17:44:53
An overall limit on the input size would be nice to have (limit on t or sum of all n*m, etc.) 

morass:
20170211 10:28:09
ANNOUNCEMENT: I'm sorry for inconvenience, but I've found wrong input. It shall be hopefully solved now! (my apologies go to "Prec" who tried to solve it with it [sorry]) Last edit: 20170211 10:28:48 

morass:
20170211 10:01:55
@Vipul Srivastava: Hope you are right  erasing "Harsh warning" then. Thank you for piloting as firsttosolve ^_^ 

Vipul Srivastava:
20170211 08:15:28
I think the test cases are right. Last edit: 20170211 08:23:10 
Added by:  Morass 
Date:  20170210 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 