A maze has open cells ., walls #, a start S and an exit E. Each move goes up, down, left or right to an open cell (or E). Print the fewest moves from S to E, or -1 if E cannot be reached.
Input
The first line has R and C (1 ≤ R, C ≤ 20). Each of the next R lines has C characters.
Output
The fewest moves, or -1.
Examples
Example 1 · Input
3 4 S..# .#.. ...E
Expected output
5
Example 2 · Input
2 2 S# #E
Expected output
-1
Hints
Hint 1
Find S and E first. BFS from S with queue<pair<int, int>>.
Hint 2
dist starts at -1 for every cell; walls (#) are never entered.
Hint 3
Check the bounds before reading grid[r][c].
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int main() {
int R, C;
cin >> R >> C;
vector<string> grid(R);
for (auto& row : grid) cin >> row;
int sr = 0, sc = 0, er = 0, ec = 0;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) {
if (grid[r][c] == 'S') sr = r, sc = c;
if (grid[r][c] == 'E') er = r, ec = c;
}
vector<vector<int>> dist(R, vector<int>(C, -1));
int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
queue<pair<int, int>> q;
q.push({sr, sc});
dist[sr][sc] = 0;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int r = cur.first + dr[k], c = cur.second + dc[k];
if (r < 0 || c < 0 || r >= R || c >= C) continue;
if (grid[r][c] == '#' || dist[r][c] != -1) continue;
dist[r][c] = dist[cur.first][cur.second] + 1;
q.push({r, c});
}
}
cout << dist[er][ec] << "\n";
return 0;
}