Flip adjacent colors in a 2D matrix

Problem

Given a 2D array of black-and-white points and an entry point, flip the color of all points connected to the entry point (including the entry point itself).

Input

• A: 2D boolean array of size greater than \(n\) \times \(m\), where False represents the color black and True represents the color white.
  • \(n\geq0, m\geq0\)
• entry: a tuple with x, y coordinates

Approach

Suppose that the entry point is in dead center of the 2D matrix \(n \times m\), where \(n = 10000\) and \(m = 10000\). If we use DFS from the entry point, at the worst case we may end up traversing to the very top of the 2D array first, only to come back all the way down to the bottom of the 2D array, and repeating this up-down movement numerous times. This results in inefficiency since some of those points are invalid (they are not the same color as the entry color), and these points may be color-grouped in big lumps.

It is much better to search the points closest to the entry point first. This makes BFS an excellent choice.

Solution

While DFS works like a stack, BFS works like a queue.
A deque is used in the solution to save performance on removing the HEAD element (as shown by .popleft(), which is similar to a queue's dequeue).

from collections import namedtuple, deque

Point = namedtuple("Point", "x  y")


def paint_matrix(A, entry):  
    entry_color = A[entry.y, entry.x]
    q = deque([entry])

    while q:
        curr = q.popleft()
        if curr.y >= 0 and curr.x >= 0 and \
            curr.y < len(A) and curr.x < len(A) and \
            A[curr.y][curr.x] == entry_color:
            # Flip color
            A[curr.y][curr.x] = not A[curr.y][curr.x]

            for direction in (Point(0, 1), Point(1, 0), Point(-1, 0), Point(0, -1)):
                q.append(Point(curr.x + direction.x, curr.y + direction.y))

    return A