import itertools

# Define a class for the game grid
class Grid:
    def __init__(self, R, C, cells):
        self.R = R
        self.C = C
        self.cells = cells
        self.starts = {}
        self.finishes = {}
        
        # Find interesting starts and finishes
        for i in range(R):
            for j in range(C):
                c = cells[i][j]
                if c.islower():
                    self.starts[c] = (i, j)
                elif c.isupper():
                    self.finishes[c] = (i, j)
        
    # Check if a cell is valid (not a wall or out of bounds)
    def is_valid(self, i, j):
        return 0 <= i < self.R and 0 <= j < self.C and self.cells[i][j] != '#'
        
    # Get possible movements from a cell
    def get_moves(self, i, j):
        moves = []
        if self.is_valid(i-1, j): # north
            moves.append((i-1, j))
        if self.is_valid(i+1, j): # south
            moves.append((i+1, j))
        if self.is_valid(i, j-1): # west
            moves.append((i, j-1))
        if self.is_valid(i, j+1): # east
            moves.append((i, j+1))
        return moves
    
    # Check if a pair is drivable
    def is_drivable(self, start, finish):
        # Create all possible misheard commands
        commands = [['north', 'south'], ['east', 'west']]
        command_permutations = itertools.product(*commands)
        
        # Check if any strategy reaches the finish with probability at least 1-10^-100
        for p in command_permutations:
            prob = self.probability(start, finish, p)
            if prob >= 1 - 1e-100:
                return True
        return False
    
    # Calculate probability of reaching finish from start with given strategy
    def probability(self, start, finish, commands):
        # Create list of possible states (cell, hazard or finish)
        states = []
        for i in range(self.R):
            for j in range(self.C):
                c = self.cells[i][j]
                if c == '*':
                    states.append('hazard')
                elif c.isupper():
                    states.append('finish')
                elif self.is_valid(i, j):
                    states.append('cell')
                else:
                    states.append('wall')
        
        # Create transition matrix
        n = len(states)
        matrix = [[0]*n for _ in range(n)]
        for i in range(n):
            if states[i] != 'cell':
                continue
            for j in self.get_moves(i//self.C, i%self.C):
                k = j[0]*self.C + j[1]
                if states[k] == 'hazard':
                    matrix[i][i] += 0.5
                    matrix[i][n-1] += 0.5
                elif states[k] == 'finish':
                    matrix[i][k] += 1
                else:
                    matrix[i][k] += 0.5
                    matrix[i][k+1] += 0.5
        
        # Calculate probability using matrix multiplication
        start_idx = self.starts[start][0]*self.C + self.starts[start][1]