To solve this problem, we need to find the shortest path from the starting position 'S' to the exit 'E' in a grid-based factory map while avoiding obstacles '#'. The solution involves using Breadth-First Search (BFS) to explore all possible paths level by level, ensuring the shortest path is found once the exit is reached.

1. Problem Analysis: The factory map is represented as a grid where each cell can be an open space ('.'), an obstacle ('#'), the start ('S'), or the exit ('E'). The goal is to navigate from 'S' to 'E' using the shortest path, moving only up, down, left, or right.
2. Intuition: BFS is suitable for this problem because it explores all neighboring cells level by level. This ensures that the first time the exit is reached, the path taken is the shortest possible.
3. Algorithm Selection: BFS is chosen for its ability to find the shortest path in an unweighted grid. The algorithm starts from 'S', explores all adjacent cells, and continues until 'E' is found or all possibilities are exhausted.
4. Complexity Analysis: The time complexity is O(rows cols) as each cell is processed at most once. The space complexity is also O(rows cols) to store the visited status and the queue.

Solution Code

import sys
from collections import deque
def main():
    data = sys.stdin.read().splitlines()
    if not data:
        print(-1)
        return
    rows, cols = map(int, data[0].split())
    grid = []
    for i in range(1, 1 + rows):
        grid.append(data[i].strip())
    start = None
    exit_pos = None
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 'S':
                start = (i, j)
            elif grid[i][j] == 'E':
                exit_pos = (i, j)
    if start is None or exit_pos is None:
        print(-1)
        return
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False] * cols for _ in range(rows)]
    queue = deque()
    queue.append((start[0], start[1], 0))
    visited[start[0]][start[1]] = True
    found = False
    while queue:
        r, c, steps = queue.popleft()
        if (r, c) == exit_pos:
            print(steps)
            found = True
            break
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if not visited[nr][nc] and grid[nr][nc] != '#':
                    visited[nr][nc] = True
                    queue.append((nr, nc, steps + 1))
    if not found:
        print(-1)
if __name__ == "__main__":
    main()

Explanation

1. Reading Input: The input is read from standard input, where the first line contains the grid dimensions (rows and columns), followed by the grid itself.
2. Locating Start and Exit: The grid is scanned to find the positions of 'S' (start) and 'E' (exit). If either is missing, the solution outputs -1 immediately.
3. BFS Initialization: The BFS starts from the 'S' position, initializing a queue with the starting coordinates and initial step count (0). A visited matrix keeps track of processed cells to avoid revisiting.
4. BFS Execution: For each cell dequeued, the algorithm checks if it's the exit. If so, the current step count is printed. Otherwise, adjacent cells (up, down, left, right) are enqueued if they are within bounds, not obstacles, and unvisited.
5. Termination: If the queue is exhausted without finding the exit, -1 is printed, indicating no valid path exists. Otherwise, the step count upon reaching 'E' is printed, representing the shortest path length.