from functools import lru_cache # Function to simulate all possible paths from a given start position to a given end position @lru_cache(maxsize=None) def simulate(start, end): # If start and end are the same position, the path is valid with probability 1 if start == end: return 1 # If the end position is a wall or hazard, the path is invalid if grid[end[0]][end[1]] != '.': return 0 # Initialize the probability of a valid path to 0 prob = 0 # Try all possible commands, accounting for the possibility of misheard commands for command in ['north', 'south', 'east', 'west']: next_pos = move(end, command) # If the next position is outside the grid or a wall, ignore the command if not is_inside(next_pos) or grid[next_pos[0]][next_pos[1]] == '#': continue # If the next position is a hazard, the path is invalid if grid[next_pos[0]][next_pos[1]] == '*': continue # Compute the probability of a valid path using recursion if command == 'north' or command == 'south': prob += 0.5 * simulate(start, next_pos) prob += 0.5 * simulate(start, move(end, opposite(command))) else: prob += 0.5 * simulate(start, next_pos) prob += 0.5 * simulate(start, move(end, opposite(command))) return prob # Function to check if a position is inside the grid def is_inside(pos): return 0 <= pos[0] < R and 0 <= pos[1] < C # Function to move the car one cell in the given direction def move(pos, direction): if direction == 'north': return (pos[0]-1, pos[1]) elif direction == 'south': return (pos[0]+1, pos[1]) elif direction == 'east': return (pos[0], pos[1]+1) else: # direction == 'west' return (pos[0], pos[1]-1) # Function to compute the opposite direction of a given direction def opposite(direction): if direction == 'north': return 'south' elif direction == 'south': return 'north' elif direction == 'east': return 'west' else: # direction == 'west' return 'east' # Read input R, C = map(int, input().split()) grid = [input() for _ in range(R)] starts = [] ends = [] # Find all interesting starts and ends for i in range(R): for j in range(C): if grid[i][j] == 'S': starts.append((i, j)) elif grid[i][j] == 'T': ends.append((i, j)) # Check all possible pairs of interesting starts and ends valid_pairs = [] for start in starts: for end in ends: if simulate(start, end) >= 1-10**(-100): valid_pairs.append((start, end)) # Print the list of valid pairs for pair in valid_pairs: print(pair[0][0]+