Givan a rectangular maze represented by a grid of characters, determine the minimum number of steps required for a rat to reach from the starting point 'S' to the cheese at position 'E'. Walls are marked with '#', and open paths are marked with '.'.

The problem is solved using Breadth-First Search (BFS), which guarantees finding the shortest path in an unweighted graph.

Each test case begins with two integers R and C representing the dimensions of the maze. Following lines contain the maze layout. There is exactly one 'S' and one 'E' in each maze.

For each test case, output the minimum steps needed to reach 'E' from 'S'. If no path exists, print "oop!".

Example input:

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

Example output:

5
1
oop!

Implementation:

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> Point;

const int MAX_SIZE = 210;

int rows, cols;
char grid[MAX_SIZE][MAX_SIZE];
int distances[MAX_SIZE][MAX_SIZE];

int findShortestPath(Point start, Point target) {
    queue<Point> queue;
    memset(distances, -1, sizeof(distances));
    
    distances[start.first][start.second] = 0;
    queue.push(start);
    
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    
    while (!queue.empty()) {
        Point current = queue.front();
        queue.pop();
        
        for (int i = 0; i < 4; ++i) {
            int newX = current.first + dx[i];
            int newY = current.second + dy[i];
            
            if (newX < 0 || newX >= rows || newY < 0 || newY >= cols ||
                grid[newX][newY] == '#' || distances[newX][newY] != -1) {
                continue;
            }
            
            distances[newX][newY] = distances[current.first][current.second] + 1;
            
            if (newX == target.first && newY == target.second) {
                return distances[newX][newY];
            }
            
            queue.push({newX, newY});
        }
    }
    
    return -1;
}

int main() {
    int cases;
    scanf("%d", &cases);
    
    while (cases--) {
        scanf("%d%d", &rows, &cols);
        
        for (int i = 0; i < rows; ++i) {
            scanf("%s", grid[i]);
        }
        
        Point start, end;
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == 'S') {
                    start = {i, j};
                } else if (grid[i][j] == 'E') {
                    end = {i, j};
                }
            }
        }
        
        int result = findShortestPath(start, end);
        
        if (result == -1) {
            printf("oop!\n");
        } else {
            printf("%d\n", result);
        }
    }
    
    return 0;
}