Scribd
Upload
4 views2 pages

Minimize Green Bricks in Pathfinding

Uploaded by

anirudhmadhavan13
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views2 pages

Minimize Green Bricks in Pathfinding

Uploaded by

anirudhmadhavan13
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

from collections import deque

def expand_row(row): expanded = [] i = 0 while i < len(row): j = i while j <


len(row) and row[j].isdigit(): j += 1 count = int(row[i:j]) brick = row[j]
[Link]([brick] * count) i = j + 1 return expanded

def min_green_bricks_to_break(n, lines): wall = [expand_row(line) for line in


lines]

# Find Source (S) and Destination (D)


for i in range(n):
for j in range(n):
if wall[i][j] == 'S':
start = (i, j)
if wall[i][j] == 'D':
end = (i, j)

# BFS: queue of (x, y, green_bricks_broken)


queue = deque()
[Link]((start[0], start[1], 0))
visited = [[False]*n for _ in range(n)]
visited[start[0]][start[1]] = True

# Directions: up, down, left, right


directions = [(-1,0), (1,0), (0,-1), (0,1)]

while queue:
x, y, broken = [Link]()

if (x, y) == end:
return broken

for dx, dy in directions:


nx, ny = x + dx, y + dy

if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:


cell = wall[nx][ny]
if cell == 'G':
visited[nx][ny] = True
[Link]((nx, ny, broken + 1))
elif cell == 'D':
visited[nx][ny] = True
[Link]((nx, ny, broken))

# If destination cannot be reached


return -1

You might also like