import sys import collections # Use sys.stdin.readline for faster input reading, as recommended for competitive programming input = sys.stdin.readline def solve(): # Read grid dimensions H (height/rows) and W (width/columns) H, W = map(int, input().split()) # Read initial state: A (initial size), Si, Sj (start row, col) A, Si, Sj = map(int, input().split()) # Read target state: B (target size), Gi, Gj (goal row, col) B, Gi, Gj = map(int, input().split()) # Read the grid map M, where '*' denotes snow and '.' denotes no snow M = [input().strip() for _ in range(H)] # Parity Check: # When moving to an adjacent cell (i', j') from (i, j), the parity of i+j changes. # If the destination cell has snow ('*'), size s becomes s+1. Parity of s changes if s is even, stays if s is odd. Incorrect: parity changes if s+1 has different parity than s, which is always true. # If the destination cell has no snow ('.') size s becomes s-1. Parity of s changes. # Let's analyze the parity of (row + col + size). # Move from (i, j, s) to (i', j', s'). # Parity of i'+j' is different from parity of i+j. # Parity of s' is different from parity of s (since s' = s+1 or s-1). # Therefore, parity of (i'+j') + s' is the SAME as parity of (i+j) + s. # (Different + Different = Same parity overall) # This means the parity of (row + col + size) must be invariant throughout any path. # Check if the start state parity matches the target state parity. start_parity = (Si + Sj + A) % 2 target_parity = (Gi + Gj + B) % 2 if start_parity != target_parity: # If parities don't match, it's impossible to reach the target state. print('No') return # Determine the maximum snowball size to keep track of in the state space. # Any path from start S to goal G must consist of some number of steps k. # The size changes by k_snow - k_nosnow. Max size increase is k, max decrease is k. # A simple path (no repeated cells) has length k <= H*W. # If we reach a state (r, c, s) where s > B + H*W, any simple path from (r,c) to (G_i, G_j) # will end with size > B. To reach size B, a path with cycles is needed to decrease size significantly. # A reasonably safe upper bound for the necessary size seems to be max(A, B) + H * W. # We track states with size up to this maximum value. S_limit is 1 + this maximum value. # Sizes tracked are in the range [1, S_limit-1]. S_max_tracked = max(A, B) + H * W S_limit = S_max_tracked + 1 # Initial state validity check # The problem constraints state 1 <= A, B <= 1000. So A is always >= 1. # Also, A <= 1000. The maximum value of S_max_tracked is 1000 + 50*50 = 3500. # S_limit is 3501. So A is always less than S_limit. No check needed for A >= S_limit initially. # Initialize BFS queue q = collections.deque() # Visited array to keep track of visited states (row, col, size). # Using a 3D list for performance. Dimensions: H x W x S_limit. # Memory check: H*W*S_limit*sizeof(bool) <= 50*50*3501 * ~24 bytes (python bool object) ~= 210 MB. This should be okay for 512 MB limit. # If memory limit is tight, could use bytearray or dictionary. try: # Attempt to allocate memory for the visited array. visited = [[[False] * S_limit for _ in range(W)] for _ in range(H)] except MemoryError: # This error might occur if S_limit is unexpectedly large or system memory is low. sys.stderr.write("Memory allocation failed. The state space might be too large.\n") # In a contest setting, this could lead to Memory Limit Exceeded. # Depending on the platform/rules, might need to exit or handle differently. # Using a dictionary `visited = {}` with keys `(r, c, s)` is an alternative, # potentially slower access but uses memory proportional to reachable states. # For now, we assume the list allocation succeeds based on estimates. exit(1) # Exit if memory allocation fails. # Add the initial state to the queue and mark it as visited. q.append((Si, Sj, A)) visited[Si][Sj][A] = True # Define the 4 possible directions (Up, Down, Left, Right) dr = [-1, 1, 0, 0] dc = [0, 0, -1, 1] found = False # Flag to indicate if the target state has been reached # Start the Breadth-First Search while q: # Dequeue the next state to explore r, c, s = q.popleft() # Check if the current state is the target state if r == Gi and c == Gj and s == B: found = True break # Target found, terminate BFS # Explore neighbors of the current cell (r, c) for i in range(4): nr, nc = r + dr[i], c + dc[i] # Calculate neighbor coordinates # Check if the neighbor cell (nr, nc) is within the grid boundaries if 0 <= nr < H and 0 <= nc < W: # Calculate the new snowball size after moving to the neighbor cell # Size increases by 1 if the cell has snow ('*'), decreases by 1 otherwise ('.') new_s = s + 1 if M[nr][nc] == '*' else s - 1 # Check if the new state is valid: # 1. Snowball size must be at least 1 (it hasn't melted). # 2. Snowball size must be less than S_limit (within the tracked range). Pruning states with large sizes. if 1 <= new_s < S_limit: # Check if this state (nr, nc, new_s) has been visited before if not visited[nr][nc][new_s]: # If not visited, mark it as visited visited[nr][nc][new_s] = True # Add the new state to the queue for exploration q.append((nr, nc, new_s)) # Implicit else: if new_s < 1 (melted) or new_s >= S_limit (too large), # this path is invalid/pruned, so we don't add it to the queue. # After the BFS completes (queue is empty or target found): # Print the result based on whether the target state was reached. if found: print('Yes') else: print('No') # Execute the main solve function solve()