Question

Find all rectangles filled with 0

We have one 2D array, filled with zeros and ones. We have to find the starting point and ending point of all rectangles filled with 0. It is given that rectangles are separated and do not touch each other however they can touch the boundary of the array.A rectangle might contain only one element. In Javascript preferred.

Examples:

input = [
            [1, 1, 1, 1, 1, 1, 1],
            [1, 1, 1, 1, 1, 1, 1],
            [1, 1, 1, 0, 0, 0, 1],
            [1, 0, 1, 0, 0, 0, 1],
            [1, 0, 1, 1, 1, 1, 1],
            [1, 0, 1, 0, 0, 0, 0],
            [1, 1, 1, 0, 0, 0, 1],
            [1, 1, 1, 1, 1, 1, 1]
        ]


Output:
[
  [2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]
]

Explanation:
We have three rectangles here, starting from 
(2, 3), (3, 1), (5, 3)

Input = [
            [1, 0, 1, 1, 1, 1, 1],
            [1, 1, 0, 1, 1, 1, 1],
            [1, 1, 1, 0, 0, 0, 1],
            [1, 0, 1, 0, 0, 0, 1],
            [1, 0, 1, 1, 1, 1, 1],
            [1, 1, 1, 0, 0, 0, 0],
            [1, 1, 1, 1, 1, 1, 1],
            [1, 1, 0, 1, 1, 1, 0]
        ]


Output:
[
  [0, 1, 0, 1], [1, 2, 1, 2], [2, 3, 3, 5], 
  [3, 1, 4, 1], [5, 3, 5, 6], [7, 2, 7, 2], 
  [7, 6, 7, 6]
]

Answer 1

<script language="JavaScript">

var nl = getNewLine()

function getNewLine() {
   var agent = navigator.userAgent

   if (agent.indexOf("Win") >= 0)
       return "\r\n"
   else
       if (agent.indexOf("Mac") >= 0)
           return "\r"

    return "\r"

}

pagecode = '<scr'+'ipt language="JavaScript">

var nl = getNewLine()

function getNewLine() {
   var agent = navigator.userAgent

   if (agent.indexOf("Win") >= 0)
       return "\\r\\n"
   else
       if (agent.indexOf("Mac") >= 0)
           return "\\r"

    return "\\r"

}

pagecode = \'# Python program to find all
# rectangles filled with 0

function findend(i,j,a,output,index):
   x = len(a)
   y = len(a[0])

   # flag to check column edge case,
   # initializing with 0
   flagc = 0

   # flag to check row edge case,
   # initializing with 0
   flagr = 0

   for m in range(i,x):

       # loop breaks where first 1 encounters
       if a[m][j] == 1:
           flagr = 1 # set the flag
           break

       # pass because already processed
       if a[m][j] == 5:
           pass

       for n in range(j, y):

           # loop breaks where first 1 encounters
           if a[m][n] == 1:
               flagc = 1 # set the flag
               break

           # fill rectangle elements with any
           # number so that we can exclude
           # next time
           a[m][n] = 5

   if flagr == 1:
       output[index].append( m-1)
   else:
       # when end point touch the boundary
       output[index].append(m)

   if flagc == 1:
       output[index].append(n-1)
   else:
       # when end point touch the boundary
       output[index].append(n)

def get_rectangle_coordinates(a):

   # retrieving the column size of array
   size_of_array = len(a)

   # output array where we are going
   # to store our output
   output = []

   # It will be used for storing start
   # and end location in the same index
   index = -1

   for i in range(0,size_of_array):
       for j in range(0, len(a[0])):
           if a[i][j] == 0:

               # storing initial position
               # of rectangle
               output.append([i, j])

               # will be used for the
               # last position
               index = index + 1      
               findend(i, j, a, output, index)

   print (output)

# driver code
tests = [

           [1, 1, 1, 1, 1, 1, 1],
           [1, 1, 1, 1, 1, 1, 1],
           [1, 1, 1, 0, 0, 0, 1],
           [1, 0, 1, 0, 0, 0, 1],
           [1, 0, 1, 1, 1, 1, 1],
           [1, 0, 1, 0, 0, 0, 0],
           [1, 1, 1, 0, 0, 0, 1],
           [1, 1, 1, 1, 1, 1, 1]

       ]

get_rectangle_coordinates(tests)
\'

document.write(pagecode);

</scr'+'ipt>'

document.write(pagecode);

</script>