"""
Simulasi Aliran Air Sampai Jauh

Program ini mensimulasikan bagaimana air mengalir dari sumber ke titik tujuan (desa)
pada grid 2D dengan ketinggian medan.

Air hanya dapat mengalir ke posisi dengan ketinggian yang sama atau lebih rendah.
"""

from collections import deque

def print_grid(grid, path=None):
    """
    Menampilkan grid. Jika path diberikan,
    sel pada jalur diberi tanda '*'.
    """
    rows = len(grid)
    cols = len(grid[0])
    for r in range(rows):
        for c in range(cols):
            if path and (r, c) in path:
                print(" * ", end="")
            else:
                print(f" {grid[r][c]:2d}", end=" ")
        print()

def find_water_flow_path(grid, start, destination):
    """
    Mencari jalur aliran air dari start ke destination.
    Air hanya boleh mengalir ke posisi dengan ketinggian <= posisi saat ini.
    Menggunakan BFS untuk mencari jalur.
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque([start])
    visited = set([start])
    parent = {start: None}

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

    while queue:
        current = queue.popleft()
        if current == destination:
            break
        curr_r, curr_c = current
        curr_height = grid[curr_r][curr_c]

        for dr, dc in directions:
            nr, nc = curr_r + dr, curr_c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if (nr, nc) not in visited and grid[nr][nc] <= curr_height:
                    visited.add((nr, nc))
                    parent[(nr, nc)] = current
                    queue.append((nr, nc))

    if destination not in parent:
        return None

    path = []
    step = destination
    while step is not None:
        path.append(step)
        step = parent[step]
    path.reverse()
    return path

if __name__ == "__main__":
    terrain = [
        [5, 5, 4, 3, 2],
        [6, 5, 4, 3, 2],
        [7, 6, 5, 3, 1],
        [8, 7, 5, 2, 1],
        [9, 8, 7, 1, 0]
    ]

    start = (0,0)
    destination = (4,4)

    print("Grid medan ketinggian:")
    print_grid(terrain)

    path = find_water_flow_path(terrain, start, destination)

    if path:
        print("\\nJalur aliran air dari sumber ke desa ditemukan:")
        print(path)
        print("\\nGrid dengan jalur aliran air ditandai '*':")
        print_grid(terrain, path=path)
    else:
        print("\\nTidak ditemukan jalur aliran air yang mengalir sampai ke desa.")