All submissions for this problem are available.
Chef likes to watch movies very much.A movie of his favorite actress has recently released and he wants to go to cinema hall with his friends to watch the movie.
But he will book tickets for him and his friends only if he gets the seats in his desired block size. eg. if he has 9 friends, then he has to book 10 tickets, and wants the seats to be in a rectangular block to 2 X 5. i.e if Chef has to book n number of seats, then the block of seats he would want is p X q where p * q = n
You are given the status of all the seats(booked or not) and you have tell the Chef the number of blocks of exact size, in which all the seats in the block are not booked, and the seat number of the top left corner of the block, so that Chef could chose one of the them.(The seat number of the seats is same as the indices of 2D matrix with base index 0)
It might be possible that no such block of empty seats is available
The first line contains the number of test cases ( 1 <= t <= 10).
First line of each test contains n and m( 1 <= n,m <= 1000) which is the size of cinema hall. Cinema hall contains (n X m) no. of seats. The next line contains by p and q separated by a space which tells the block size non-booked seats that Chef wants.
It is followed by n lines where each line contains m characters. A booked seat is denoted by '.' and an available seat is denoted by '#' .
The first line of output of each test case should consist of the number of available blocks of empty seats( e ) i.e the number of blocks of p X q that have no booked seats.
It should be followed by e number of lines where each line contains a and b (0 <= a < n , 0 <= b < m) denoting the top left corner of the block of size p X q having all seats non-booked.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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