Museum Security algorithm challenge

Question

Suppose you've been asked to verify a museum's security is up to standard.

You're given a floor plan with the positions of all guards and walls:

4 6
0 0 g
0 1 w
1 1 g
2 2 w
2 3 g

The first line describes the dimensions of the museum, which is a m x n rectangle (in this case, 4 x 6). m and n are always greater than 0.

Subsequent lines correspond to positions of guards (designated as "g") and walls (designated as "w"). For example, "0 0 g" designates there is a guard at (0, 0).

Guards do not move, but can guard any line of rooms that are:

directly to the north, east, south, or west of them
unobstructed (i.e., there is no wall in between them)

For example, the guard at (0, 0) can only guard (1, 0), (2, 0), and (3, 0).

Whereas the guard at (2, 3) can guard (0, 3), (1, 3), (2, 4), (2, 5), and (3, 3).

The above museum looks something like:

  0 1 2 3 4 5 

0 g w   -     
1 - g - - - - 
2 - - w g - - 
3 - -   -     

Guarded rooms have been marked with a "-".

Given a museum, please print your solution in the following format:

false
0 2
0 4
0 5
3 2
3 4
3 5

The first line should be "false" if the museum has unguarded rooms, and "true" if the museum has no unguarded rooms.

If "false", subsequent lines should be coordinates of unguarded rooms.

Unguarded rooms should be ordered in ascending order by (x, y).

What I have tried so far

def checkUnguarded(arr, v)
    i = 0
    while i < arr.length do
        j = 0
        while j < arr[0].length do
            if(arr[i][j]=='g')
                r=i
                c=j
                k=r-1
                while(k>=0&&(arr[k][c]=='w')) do
                    v[k][c]=true
                    k -= 1
                end
                k=r+1
                while(k<arr.length&&(arr[k][c]=='w')) do
                    #binding.pry
                    v[k][c]=true

                    k += 1
                end
                k=c+1
                while(k < arr[0].length && (arr[r][k]) == 'w') do
                    v[r][k]=true;

                    k += 1
                end
                k=c-1
                while(k>=0 && (arr[r][k])=='w') do
                    
                    v[r][k]=true
                    k -= 1
                end
            end
            j += 1
        end
        i += 1
    end
end

arr = [
    [0, 0, 'g'],
    [0, 1, 'w'],
    [1, 1, 'g'],
    [2, 2, 'w'],
    [2, 3, 'g']
]

v = [
    [0, 0],
    [0, 0],
    [0, 0],
    [0, 0],
    [0, 0],
]

puts(checkUnguarded(arr, v))

Currently I tried with brute force. Some edge cases are failing

Answer 1

It suffices to find which rooms are guarded from the north, which from the east, which from the south, which from the west, and merge the results.

Considering one cardinal direction at a time, this 2D problem becomes a collection of independent 1D problems.

To solve one of these 1D problems – determining which rooms are guarded from the west, for example – we sweep west to east, maintaining a flag that indicates whether there is a guard to the west with an unobstructed view of the current room. Initially false, this flag becomes true when we scan a guard and false when we scan a wall.