Finding the amount of 'water' captured by grid-CodePudding

Given some m by n grid of 1's and 0's, how would you find how much water would be captured by it, where the 1's are 'walls', and 0's are empty space?

Examples:

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

This grid would capture 9 units of water.

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

However, because this grid has a 'leak' in one of its walls, this would capture 0 units of water.

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

Likewise, because there is a partition between the two sections, the leaky one does not affect the other, and as such this grid would capture 3 units of water.

I'm just really uncertain of how to start on this problem. Are there any algorithms that would be helpful for this? I was thinking depth-first-search or some sort of flood-fill, but now I'm not sure if those are applicable to this exercise.

CodePudding user response：

You can create a list of leaks starting from the positions of 0s on the edges. Then expand that list with 0s that are next to the leaking positions (until no more leaks can be added). Finally, subtract the number of leaks from the total number of zeros in the grid.

def water(G):
    rows = len(G)
    cols = len(G[0])  
    # initial leaks are 0s on edges
    leaks = [ (r,c) for r in range(rows) for c in range(cols)
              if G[r][c]==0 and (r==0 or c==0 or r==rows-1 or c==cols-1) ]
    for r,c in leaks:
        for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]: # offsets of neighbours
            nr,nc = r dr, c dc                    # coordinates of a neighbour
            if nr not in range(rows): continue    # out of bounds
            if nc not in range(cols): continue    # out of bounds
            if G[nr][nc] != 0: continue           # Wall
            if (nr,nc) in leaks: continue         # already known
            leaks.append((nr,nc))                 # add new leak
    return sum( row.count(0) for row in G) - len(leaks)

Output:

grid = [[1, 1, 1, 1, 1],
        [1, 0, 0, 0, 1],
        [1, 0, 0, 0, 1],
        [1, 0, 0, 0, 1],
        [1, 1, 1, 1, 1]]
print(water(grid)) # 9

grid = [[1, 1, 1, 0, 1],
        [1, 0, 0, 0, 1],
        [1, 0, 0, 0, 1],
        [1, 0, 0, 0, 1],
        [1, 1, 1, 1, 1]]
print(water(grid)) # 0

grid = [[1, 1, 1, 0, 1],
        [1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1],
        [1, 1, 1, 1, 1]]
print(water(grid)) # 3

Note that this only looks for leaks in horizontal and vertical (but not diagonal) directions. To manage leaking through diagonals, you'll need to add (-1,-1),(-1,1),(1,-1),(1,1) to the list of offsets.

CodePudding user response：

Removing zeros starting at the edges, representing the coordinates of zeros with a set (for fast lookup) of complex numbers (for easy neighbor calculation):

def water(G):
    m, n = len(G), len(G[0])
    zeros = {complex(i, j)
             for i in range(m) for j in range(n)
             if G[i][j] == 0}
    for z in list(zeros):
        if z.real in (0, m-1) or z.imag in (0, n-1):
            q = [z]
            for z in q:
                if z in zeros:
                    zeros.remove(z)
                    for a in range(4):
                        q.append(z   1j**a)
    return len(zeros)

Or with Alain's style of a single BFS, initializing the queue with all edge zeros:

def water(G):
    m, n = len(G), len(G[0])
    zeros = {complex(i, j)
             for i in range(m) for j in range(n)
             if G[i][j] == 0}
    q = [z for z in zeros
         if z.real in (0, m-1) or z.imag in (0, n-1)]
    for z in q:
        if z in zeros:
            zeros.remove(z)
            for a in range(4):
                q.append(z   1j**a)
    return len(zeros)