import collections import sys def solve(): # Read input using sys.stdin.readline for potentially faster I/O r, c = map(int, sys.stdin.readline().split()) sy, sx = map(int, sys.stdin.readline().split()) gy, gx = map(int, sys.stdin.readline().split()) # Adjust coordinates to be 0-based for list indexing start_y, start_x = sy - 1, sx - 1 goal_y, goal_x = gy - 1, gx - 1 # Read the maze grid maze = [sys.stdin.readline().strip() for _ in range(r)] # Initialize distance grid. -1 means unvisited. # Using a list of lists for the distance grid. dist = [[-1] * c for _ in range(r)] # Initialize a deque (double-ended queue) for BFS # Store coordinates as tuples (y, x) queue = collections.deque() # Start BFS from the starting point # Set distance to start as 0 and add it to the queue dist[start_y][start_x] = 0 queue.append((start_y, start_x)) # Define possible moves (up, down, left, right) # dy corresponds to changes in row index (y) # dx corresponds to changes in column index (x) dy = [-1, 1, 0, 0] dx = [0, 0, -1, 1] # BFS main loop while queue: # Dequeue the next cell to visit y, x = queue.popleft() # If we reached the goal, we found the shortest path if y == goal_y and x == goal_x: print(dist[y][x]) return # Exit the function after printing the result # Explore neighbors for i in range(4): ny, nx = y + dy[i], x + dx[i] # Check if the neighbor is within the grid boundaries if 0 <= ny < r and 0 <= nx < c: # Check if the neighbor is an empty cell ('.') # and if it hasn't been visited yet (dist == -1) if maze[ny][nx] == '.' and dist[ny][nx] == -1: # Mark the neighbor as visited by setting its distance dist[ny][nx] = dist[y][x] + 1 # Enqueue the neighbor queue.append((ny, nx)) # Call the solve function to run the code solve()