IITKESO207SPA3D - Largest bunch of zeros
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.
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.
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 )
3 4 4
0 3 1 1 1 2 2 0
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.
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.
Last edit: 2017-07-05 13:50:10
Please note that this assignment is visible and solvable for the general public.
Programming Club, IITK:
Description has been updated, thank you for pointing out the error.
sample test case is invalid but test cases are valid
The given sample test case is:
If row = 3 and Column =4
Programming Club, IITK:
Sort the top left vertex of each answer by their row, and then by column. Print the first answer from this ordering.
There can be multiple answers, whose co-ordinates we need to print then?Last edit: 2017-06-28 08:40:56