Reach matrix boundary with color transition rules
Filed under OYO
Free read 2 of 3Verify movement rules and confirm whether reaching any edge cell immediately returns true.
The question
Given an m x n matrix containing 'B' (Black), 'W' (White), and 'U' (Uncolored), starting at a given coordinate (i, j), determine if you can reach any boundary of the matrix. Movement is allowed in 4 directions. Transition rules: from 'B' go only to 'B' or 'U'; from 'W' go only to 'W' or 'U'; from 'U' go to any color.
Constraints
- Matrix dimensions m, n <= 500
- Valid cell values are strictly 'B', 'W', or 'U'
Examples
- Input
- matrix = [['B', 'U'], ['W', 'W']], start = (0, 0)
- Output
- True
- Why
- Can move from (0,0) 'B' to (0,1) 'U' which is on the boundary.
Approach
Verify movement rules and confirm whether reaching any edge cell immediately returns true.
Explore all paths using standard traversal without tracking visited states, leading to exponential time complexity.
Use Breadth-First Search (BFS) or Depth-First Search (DFS) with a visited matrix, respecting the color transition rules at each step.
Start position already on the boundary, unreachable regions, and single-cell matrices.
Solution
O(m * n) time, O(m * n) space
from collections import deque
def can_reach_boundary(matrix, start):
m, n = len(matrix), len(matrix[0])
si, sj = start
if si == 0 or si == m-1 or sj == 0 or sj == n-1:
return True
queue = deque([start])
visited = {start}
while queue:
r, c = queue.popleft()
if r == 0 or r == m-1 or c == 0 or c == n-1:
return True
curr_color = matrix[r][c]
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited:
next_color = matrix[nr][nc]
if curr_color == 'U' or next_color == 'U' or curr_color == next_color:
visited.add((nr, nc))
queue.append((nr, nc))
return False
Tips
- What they are testing: Test scenarios where the start is already on the boundary, and cases where color constraints completely block paths.
- Common mistake: Forgetting to mark visited nodes, which leads to infinite loops in cyclic color transitions.
Follow-ups
- What would happen if DFS were used instead of BFS? Will the best-case improve?
Related OYO questions
Collected from public candidate posts and coding forums. Updated Nov 2026.