Find all possible rectangles based on point in 2D Grid

Question

I got the following map

local Map = {
    [1] = {
        [1] = 'Sand',
        [2] = 'Sand',
        [3] = 'Sand'
    },
    [2] = {
        [1] = 'Sand',
        [2] = 'Sand',
        [3] = 'Grass'
    },
    [3] = {
        [1] = 'Rock',
        [2] = 'Rock',
        [3] = 'Grass'
    },
}

The map above:

S = Sand
G = Grass
R = Rock

S S R
S S R
S G G

and try to make a function which I supply a point and it returns me an array of all possible rectangles with that type.

Something like

function GetRectangles(X, Y)
local Type = Map[X][Y]
local Result = {}
-- Get all rectangles with same type and add to array
return Result
end

So, when I call GetRectangles(1, 1), it returns me an array with the following rectangles

• Rectangle starting at 1, 1 and ending at 2, 2
• Rectangle tarting at 1, 1 and ending at 1, 3

And when I call GetRectangles(3, 3), it returns me an array with the following content

• Rectangle starting at 3, 3 and ending at 2, 3

How would I do this?

Answer 1

Consider Backtracking.

recursive step:
    for each step in possible steps:
        check new rectangle for single type
            if ok, add to rectangle list and recurse

where possible steps are : add 1 column to the left, add 1 column to the right, add 1 row to above, add 1 row below.

example:

current rectangle (1,1), (1,1)
   rectangle is ok
   add 1 row below:
   current rectangle (1,1), (1,2)
       rectangle is ok, add
       add 1 row below
            current rectangle (1,1) (1,3)
            rectangle ok, add
            // add 1 row below not possible step
            add 1 column left  
            rectangle (1,1) (2,3) not ok
            no more steps    
       add 1 column left
       rectangle (1,1) (2,1) not ok
       no more steps
   etc...

for overlaps, iterate over list and remove them or hint: this can be done during iteration.