def build_graph(grid):
    graph = {}
    for r, row in enumerate(grid):
        for c, cell in enumerate(row):
            if cell != '#':
                graph[(r, c)] = []
                if r > 0 and grid[r-1][c] != '#':
                    graph[(r, c)].append((r-1, c))
                if r < len(grid)-1 and grid[r+1][c] != '#':
                    graph[(r, c)].append((r+1, c))
                if c > 0 and grid[r][c-1] != '#':
                    graph[(r, c)].append((r, c-1))
                if c < len(row)-1 and grid[r][c+1] != '#':
                    graph[(r, c)].append((r, c+1))
    return graph

def compute_probabilities(graph, grid, starts):
    prob_table = {}
    for start in starts:
        visited = set()
        stack = [(start, 1)]
        while stack:
            node, prob = stack.pop()
            if node in visited:
                continue
            visited.add(node)
            if node not in prob_table:
                prob_table[node] = {}
            prob_table[node][start] = max(prob, prob_table[node].get(start, 0))
            for neighbor in graph[node]:
                if grid[neighbor[0]][neighbor[1]] == '*':
                    continue
                if grid[neighbor[0]][neighbor[1]] in 'NS':
                    stack.append((neighbor, prob * 0.5))
                elif grid[neighbor[0]][neighbor[1]] in 'WE':
                    stack.append((neighbor, prob * 0.5))
                else:
                    stack.append((neighbor, prob))
    return prob_table

def dfs(graph, grid, start, finish, prob, visited, drivable_pairs):
    if start == finish:
        if prob >= 1 - 10**-100:
            drivable_pairs.add((grid[start[0]][start[1]], grid[finish[0]][finish[1]]))
        return
    if start in visited:
        return
    visited.add(start)
    for neighbor in graph[start]:
        if grid[neighbor[0]][neighbor[1]] == '*':
            continue
        if grid[neighbor[0]][neighbor[1]] in 'NS':
            dfs(graph, grid