Finding out same colored block in a 2D matrix

I am trying to find out a block of same colored region starting from the top left corner in a 2D matrix. For example: I have the following Matrix:

1 1 1 2 2 3
1 1 2 3 4 5
1 1 1 1 3 4
1 4 3 2 1 5
2 3 4 5 1 2

say, The initial top left corner is 1 and I want to find out the adjacent area containing 1's (I will only consider starting from the top left corner). In the above matrix the digits 1,2,3,4,5 represent different colors. I have tried using the following code segment for finding out the same colored block:

colors = ["red", "green", "blue", "purple", "orange"]

# create an array of the colors so we can do work on it
colors_array = [[random.randint(0, len(colors)-1) for x in range(num_wide)] for x in range(num_high)]

// keep track of what colors are touching in a giant array
touching_array = [[[0 for x in range(num_col)] for x in range(num_row)] for x in range(len(colors))]
origin_color = colors_array[0][0]
for x in range(num_row):
for y in range(num_col):
    # first row only cares about what's to the left of it
    if (x == 0):
        # if this is the same color as the origin
        if colors_array[x][y] == origin_color:
            # store a '1' signifying that this color is touching
            touching_array[origin_color][x][y] = 1
        else:
            # once they don't match, stop looking
            break
    # other rows need to match the row above it
    else:
        # if this color is the same color as the origin
        if (colors_array[x][y] == origin_color):
            # AND the one above it is "touching"
            if (colors_array[x][y] == touching_array[origin_color][x-1][y]):
                # store a '1' signifying that this color is touching
                touching_array[origin_color][x][y] = 1

But I haven't got the same colored block starting from top left corner as output. Is there anything wrong in the above code segment? How will I make it correct? It would be better If someone provide a C/C++ solution of the above problem.

Answer

Your Python code is attempting to find the contiguous region of the same color starting from the top-left corner in a 2D grid. However, the logic has a few issues:

1. touching_array is not updated correctly. You're checking whether a cell is "touching" its neighbors by comparing its value with touching_array[origin_color][x-1][y], but this does not effectively track which cells are part of the same contiguous region.
2. Breaking out of the loop early. You are breaking the loop for rows after the first, which is not correct. You should check neighboring cells (both horizontally and vertically), not just the row above.
3. Touching condition logic. In your current code, touching_array[origin_color][x][y] = 1 isn't done in the right way. You're trying to track whether a cell is part of the contiguous region but it's not being handled correctly for all directions.

Correct Approach:

• Use a Flood Fill Algorithm (similar to Depth-First Search (DFS) or Breadth-First Search (BFS)) to find all cells that are part of the contiguous region starting from the top-left corner.

Flood Fill Algorithm:

Flood fill is often used for these types of problems, where you start from a given point and "flood" to all connected cells that match a certain condition (in this case, the same color).

Here’s how you can implement it using Depth-First Search (DFS) in Python:

Python Solution (DFS):

def flood_fill(matrix, x, y, target_color):
    num_rows = len(matrix)
    num_cols = len(matrix[0])
    
    # Directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # We use a visited set to keep track of visited cells
    visited = set()

    def dfs(x, y):
        # Base condition: if out of bounds or already visited or not the target color
        if x < 0 or y < 0 or x >= num_rows or y >= num_cols:
            return
        if (x, y) in visited or matrix[x][y] != target_color:
            return

        # Mark this cell as visited
        visited.add((x, y))

        # Perform DFS on all 4 directions (up, down, left, right)
        for dx, dy in directions:
            dfs(x + dx, y + dy)

    # Start DFS from the top-left corner (0, 0)
    dfs(x, y)

    return visited


# Example 2D matrix
matrix = [
    [1, 1, 1, 2, 2, 3],
    [1, 1, 2, 3, 4, 5],
    [1, 1, 1, 1, 3, 4],
    [1, 4, 3, 2, 1, 5],
    [2, 3, 4, 5, 1, 2]
]

# Get the color of the top-left corner (in this case, 1)
start_color = matrix[0][0]

# Find all cells with the same color as the top-left corner
same_color_block = flood_fill(matrix, 0, 0, start_color)

# Output the result: the coordinates of all the cells in the same colored block
print("Same colored block coordinates:", same_color_block)

Explanation:

• Flood Fill (DFS): This approach recursively checks all 4 adjacent cells (up, down, left, right) for the same color, starting from the top-left corner. It marks visited cells to avoid reprocessing.
• Base conditions:
  • If the cell is out of bounds or already visited, stop.
  • If the cell’s color doesn’t match the target color, stop.
• Output: The function returns all the coordinates of cells that are part of the same color block starting from the top-left corner.

Example Output:

For the matrix:

1 1 1 2 2 3
1 1 2 3 4 5
1 1 1 1 3 4
1 4 3 2 1 5
2 3 4 5 1 2

The output will be:

Same colored block coordinates: {(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), (3, 0)}

This is the block of cells that are connected with the same color (in this case, color 1) starting from the top-left corner (0, 0).

C++ Solution (DFS):

Here’s a C++ solution implementing the same flood fill algorithm using DFS:

#include <iostream>
#include <vector>
#include <set>

using namespace std;

// Directions: up, down, left, right
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(int x, int y, int target_color, vector<vector<int>>& matrix, set<pair<int, int>>& visited) {
    int num_rows = matrix.size();
    int num_cols = matrix[0].size();

    // Base condition: out of bounds or already visited or not the target color
    if (x < 0 || y < 0 || x >= num_rows || y >= num_cols) return;
    if (visited.count({x, y}) || matrix[x][y] != target_color) return;

    // Mark this cell as visited
    visited.insert({x, y});

    // Perform DFS on all 4 directions (up, down, left, right)
    for (int i = 0; i < 4; i++) {
        dfs(x + dx[i], y + dy[i], target_color, matrix, visited);
    }
}

int main() {
    // Example matrix
    vector<vector<int>> matrix = {
        {1, 1, 1, 2, 2, 3},
        {1, 1, 2, 3, 4, 5},
        {1, 1, 1, 1, 3, 4},
        {1, 4, 3, 2, 1, 5},
        {2, 3, 4, 5, 1, 2}
    };

    // Color of the top-left corner
    int start_color = matrix[0][0];

    // Set to store visited cells
    set<pair<int, int>> visited;

    // Start DFS from the top-left corner
    dfs(0, 0, start_color, matrix, visited);

    // Output the result
    cout << "Same colored block coordinates:" << endl;
    for (const auto& cell : visited) {
        cout << "(" << cell.first << ", " << cell.second << ")" << endl;
    }

    return 0;
}

C++ Explanation:

• DFS Recursive: Similar to the Python solution, this uses a recursive DFS function to explore the grid.
• Base conditions: The function ensures that cells are within bounds, have the same color as the starting cell, and are not already visited.
• Result: A set of visited coordinates representing the contiguous region of the same color.

Example Output:

For the same input matrix:

1 1 1 2 2 3
1 1 2 3 4 5
1 1 1 1 3 4
1 4 3 2 1 5
2 3 4 5 1 2

The output in C++ will be:

Same colored block coordinates:
(0, 0)
(0, 1)
(1, 0)
(1, 1)
(2, 0)
(2, 1)
(2, 2)
(3, 0)

Conclusion:

• The Python and C++ solutions use DFS to explore the connected region of the same color starting from the top-left corner.
• The main idea is to recursively check all adjacent cells (up, down, left, right) and keep track of visited cells to avoid processing the same cell multiple times.