matrix.count_islands_in_matrix

Classes

Matrix

This public class represents the 2-Dimensional matrix to count

Module Contents

class matrix.count_islands_in_matrix.Matrix(row: int, col: int, graph: list[list[bool]])

This public class represents the 2-Dimensional matrix to count the number of islands.An island is the connected group of 1s,including the top, down, right, left as well as the diagonal connections. >>> matrix1 = Matrix(3, 3, [[1, 1, 0], [0, 1, 0], [1, 0, 1]]) >>> matrix1.count_islands() 1 >>> matrix2 = Matrix(2, 2, [[1, 1], [1, 1]]) >>> matrix2.count_islands() 1

count_islands() → int

This counts all the islands in the given matrix. Returns:

int: the number of islands in the given matrix.

Example - >>> mat = Matrix(1, 1, [[1]]) >>> mat.count_islands() 1 >>> mat2 = Matrix(2, 2, [[0, 0], [0, 0]]) >>> mat2.count_islands() 0

Two 1s that only touch on a diagonal still form a single island:

>>> Matrix(2, 2, [[1, 0], [0, 1]]).count_islands()
1

Two islands separated by a column of water:

>>> Matrix(3, 3, [[1, 0, 1], [1, 0, 1], [0, 0, 1]]).count_islands()
2

count_islands seeds a new island only on cells equal to 1. Before is_safe was aligned to the same rule it expanded into any truthy cell, so a matrix containing values other than 0/1 reported the wrong count. Here two 1``s are bridged by a ``2: because a 2 is not part of an island they must be counted as two separate islands. The old truthy check absorbed the 2 and merged them into one, returning 1 instead of 2:

>>> Matrix(1, 3, [[1, 2, 1]]).count_islands()
2

A lone 2 is likewise not an island:

>>> Matrix(1, 1, [[2]]).count_islands()
0

diffs(i: int, j: int, visited: list[list[bool]]) → None

This is the recursive function to mark all the cells visited which are connected to (i, j) indices. Args:

i (int): row index j (int): column index visited (list[list[bool]]): 2D list tracking the visited cells

>>> visited = [[False, False], [False, False]]
>>> graph = [[1, 1], [0, 1]]
>>> m = Matrix(2, 2, graph)
>>> m.diffs(0, 0, visited)
>>> visited
[[True, True], [False, True]]

is_safe(i: int, j: int, visited: list[list[bool]]) → bool

This checks if the current cell can be included in the current island. Args:

i (int): row index j (int): column index visited (list[list[bool]]): 2D list tracking the visited cells

Returns:

bool: True if the cell is in bounds, not yet visited and part of an island (its value is 1); False otherwise.

>>> visited = [[False, False], [False, False]]
>>> graph = [[1, 0], [0, 1]]
>>> m = Matrix(2, 2, graph)
>>> m.is_safe(0, 0, visited)
True
>>> m.is_safe(0, 1, visited)
False

A cell that is out of bounds is never safe:

>>> m.is_safe(-1, 0, visited)
False
>>> m.is_safe(0, 2, visited)
False

Only cells whose value is exactly 1 are part of an island, so any other value (e.g. 2) is treated as water, matching the seeding rule used by count_islands:

>>> m2 = Matrix(1, 1, [[2]])
>>> m2.is_safe(0, 0, [[False]])
False

COL

ROW

graph