#!/usr/bin/env python3
"""Auto-generated by AGI Loop cycle #1106
Task: cử

</think>

Write a Python function that calculates the shortest path from Eden to Daddy's home using a simplified 2D grid map with obstacles, given starting and ending coordinates.
Generated: 2026-02-12T20:26:08.177621
"""

import heapq

def shortest_path(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right

    # Priority queue: (distance, x, y)
    pq = [(0, start[0], start[1])]
    visited = set()
    path = {}

    while pq:
        dist, x, y = heapq.heappop(pq)
        if (x, y) == end:
            # Reconstruct path
            path_list = []
            curr = (x, y)
            while curr != start:
                path_list.append(curr)
                curr = path[curr]
            path_list.append(start)
            path_list.reverse()
            return path_list

        if (x, y) in visited:
            continue
        visited.add((x, y))

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0 and (nx, ny) not in visited:
                heapq.heappush(pq, (dist + 1, nx, ny))
                path[(nx, ny)] = (x, y)

    return "No path found"

if __name__ == '__main__':
    # Grid: 0 = path, 1 = obstacle
    grid = [
        [0, 0, 0, 0, 1],
        [0, 1, 1, 0, 1],
        [0, 0, 0, 0, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 0, 0]
    ]
    start = (0, 0)
    end = (4, 4)
    path = shortest_path(grid, start, end)
    print("Shortest path from Eden to Daddy's home:")
    print(path)