CODEWITHSUNDEEP
pythonlistmatrix
Guolf3377
Guolf3377

Reputation: 107

Check if matrix elements are continuous

I've been trying to solve this for days and I haven't been able to solve it.

I need to check if elements in a matrix are continuous or not. For example:

1 0 1 0 0 0
0 1 0 0 1 0
0 0 1 1 0 0

In this case, the 1 are connected because they are continuous.

Check this example:

1 0 0 0 1
0 1 0 0 1
1 0 0 0 1
0 0 1 0 0

In this case, the 1 are not continuous because they are not connected. As you can see, the matrix size varies.

Upvotes: 1

Views: 788

Answers (2)

frnhr
frnhr

Reputation: 12903

A bit of recursion will do the trick.

Here is a description of the algorithm:

  1. find a 1
  2. mark it as 0
  3. move to all adjacent cells
  4. in all of the adjacent cells that are a 1, repeat from point 2.
  5. when there is nowhere to go, find a 1 again - if found then matrix is not connected

To clarify last point - if there are any 1s remaining in the matrix, that means that our algorithm didn't reach it. And since it's moving only to adjacent cells, we conclude that the remaining 1 was not connected to initial 1 from step 1.

Here is the code:

def find_a_1():
    for row_i, row in enumerate(matrix):
        if '1' in row:
            return {
                'row': row_i,
                'col': row.index('1'),
            }

def walk_the_matrix(point):
    """ Clear current point and move to adjacent cells that are "1s" """
    # check if this is a valid cell to work on:
    try:
        if point['row'] < 0 or point['col'] < 0:
            raise IndexError  # prevent negative indexes
        if matrix[point['row']][point['col']] == '0':
            return  # nothing to do here, terminate this recursion branch
    except IndexError:
        return  # we're outside of the matrix, terminate this recursion branch
    # clear this cell:
    matrix[point['row']][point['col']] = '0'
    # recurse to all 8 directions:
    for i in (-1, 0, 1):
        for j in (-1, 0, 1):
            if (i, j) == (0, 0):
                continue
            walk_the_matrix({
                'row': point['row'] + i,
                'col': point['col'] + j,
            });

Example:

matrix = [
    list('001001'),
    list('010000'),
    list('001110'),
    list('110000'),
]

starting_point = find_a_1()

walk_the_matrix(starting_point)

if find_1() is None:
    print("The matrix is connected")
else:
    print("The matrix is not connected")

Note that this mutates the matrix list.

Upvotes: 2

FuzzyDuck
FuzzyDuck

Reputation: 1521

Edited as I misread the original question

The problem seems to boil down to, "are there any 1s completely surrounded by 0s?".

A neat way I to count the number of cells which are >1 surrounding each cell is using 2D convolution, assuming that my_array consists of 0s and 1s.

import numpy as np
import scipy.signal as ss

kernel = np.ones((3,3))

count = ss.convolve2d(my_array, kernel, mode='same') # Count number of 1s around each cell
contig = my_array * count # Remove counts where the 'centre cell' is zero

To check if my_array has any isolated 1s, simply check for any 1s in contig:

test_contig = sum(contig[contig==1]) > 0

Upvotes: 1

Related Questions