from collections import deque

def find_paths(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    visited = set()
    parent = {}
    queue = deque([start])
    visited.add(start)

    while queue:
        curr = queue.popleft()

        if curr == end:
            break

        row, col = curr
        neighbors = [(row-1, col), (row+1, col), (row, col-1), (row, col+1)]

        for neighbor in neighbors:
            n_row, n_col = neighbor

            if 0 <= n_row < rows and 0 <= n_col < cols and grid[n_row][n_col] != '#' and neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = curr
                queue.append(neighbor)

    if end not in parent:
        return 'NONE'

    paths = []
    while end != start:
        paths.append(end)
        end = parent[end]

    paths.append(start)
    return ' '.join(map(lambda x: grid[x[0]][x[1]], paths[::-1]))

# Sample input
grid = [
    ['a', '.', '.', 'c'],
    ['*', '.'],
    ['.', 'Y', '.', '#'],
    ['b', 'X', '#', 'Z']
]
start_end_pairs = [
    [(0, 1), (0, 2)],
    [(2, 1), (0, 1)],
    [(1, 1), (1, 2)],
    [(0, 0), (3, 1)]
]

# Sample output
for i, (start, end) in enumerate(start_end_pairs):
    print(f'Case #{i+1}: {find_paths(grid, start, end)}')