IITKESO207SPA3D  Largest bunch of zeros
Problem description
You are given a mxn binary matrix (contains only 1s and 0s). You have to use dynamic programming to find the largest contiguous square containing only zeros in the matrix.
Input format
The input will contain two lines. The first line will contain three integers m n x which denote the row size, column size, and number of 1s in the matrix. The second line will consist of x pairs of integers, each denoting the location of a 1 in the matrix.
Output format
You are required to print out two pairs of coordinates, that denote the top left and the bottom right of the square formed by the contiguos set of zeros. If there are multiple solutions, print the rectangle sorted by the coordinates of the top left vertex, first along row number, then along column.
In case the solution is not present, print just one integer 0. In case the solution is just one square, print starting and ending as the same point (so you would print x y x y if the square is located at x y )
Sample input
3 4 4
0 3 1 1 1 2 2 0
Sample output
0 0 0 0
Notice that here there are two rectangles with the largest size, but the one printed is the one with top left vertex sorted according to row index, and then along column index.
Scoring method
Please note that apart from the sample test case posted here, there will be other hidden test cases that your code will checked on. The final score you see is a percentage of the test cases you have passed. If you pass only the sample test case, you will get 0/100 (even though your score will be shown as 10/100).
Each of these questions are finally worth the points mentioned in the assignment pdf file. So your credit for this problem shall be your score/100 * points for this question. Your final credit for programming assignment 3 shall be final score / 55 * 100.
Plagiarism and copying
Strict action will be taken against students who are found to be indulging in plagiarism. Please note that changing variable names, removing indentation or moving code around will not help with regards to plagiarism checking.
hide comments
daud_spoj2015:
20170703 21:31:56
Last edit: 20170705 13:50:10 

wisfaq:
20170702 15:13:20
Please note that this assignment is visible and solvable for the general public.


Programming Club, IITK:
20170630 05:11:38
Description has been updated, thank you for pointing out the error. 

alpha_codeboy:
20170629 21:28:55
sample test case is invalid but test cases are valid 

pawanrocks:
20170629 16:14:34
The given sample test case is:


vipiitk:
20170629 10:56:46
If row = 3 and Column =4


Programming Club, IITK:
20170629 07:19:53
Sort the top left vertex of each answer by their row, and then by column. Print the first answer from this ordering. 

alpha_codeboy:
20170627 21:52:50
There can be multiple answers, whose coordinates we need to print then? Last edit: 20170628 08:40:56 
Added by:  Programming Club, IITK 
Date:  20170627 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  ESO207, IIT Kanpur Summer Semester 2017 