Grid Connectivity With Obstacles

EasyPython

Problem

A binary field map from the Farmer's Business Network platform marks traversable areas with 1 and blocked areas with 0. Given two coordinates, determine whether one marked cell can reach the other by moving only through adjacent marked cells.

You may move one step up, down, left, or right. Diagonal movement is not allowed, and every visited cell must contain 1.

Formal Specification

Implement can_connect(grid, start, end):

grid is a non-empty rectangular 2D array of integers containing only 0 and 1.
start and end are coordinate arrays in the form [row, column].
Both coordinates are within the grid and contain 1.
Return True if a path of horizontally or vertically adjacent 1 cells connects start to end; otherwise return False.

A breadth-first search is suitable because the task asks whether two vertices in an implicit grid graph belong to the same connected region. Mark cells as visited so each cell is processed at most once.

Constraints

1 <= rows, columns <= 1000
grid is a non-empty rectangular matrix
Each grid value is either 0 or 1
start and end are valid coordinates containing 1
Movement is limited to four orthogonal directions

Function Signature

def can_connect(grid, start, end):

You may move one step up, down, left, or right. Diagonal movement is not allowed, and every visited cell must contain 1.

Formal Specification

Implement can_connect(grid, start, end):

grid is a non-empty rectangular 2D array of integers containing only 0 and 1.
start and end are coordinate arrays in the form [row, column].
Both coordinates are within the grid and contain 1.
Return True if a path of horizontally or vertically adjacent 1 cells connects start to end; otherwise return False.