Maze walking

Original link ： A bouquet for Algernon

The main idea of the topic ： Given a $N\times M$ The maze described by the character matrix （‘#’ Wall ,‘.’ To show that one can pass through ）, There must be only one starting point $S$ And the end $E$. Find the shortest distance from the beginning to the end , If not, output “oop!”.

Tips ：

• How to read the map

char g[N][N];
for (int i = 0; i < n; i ++) cin >> g[i]; // Read in one string at a time （ One dimensional array ）

• Enumeration direction

int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};
for (int i = 0; i < 4; i ++)
{
    
	int x = t.x + dx[i], y = t.y + dy[i]; //(x, y) Is the coordinate of the currently processed adjacency point ,(t.x, t.y) Is the coordinate of the origin 
	...
}

• dist The array is used to record the distance from each reachable point to the starting point , Initialize to -1, At the same time, it also plays st Duplicate judgment of array .

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

const int N = 210;
char g[N][N];
int dist[N][N];

int n, m; // Maze scale 

int bfs(PII start, PII end) // Pass in the coordinates of the start and end points 
{
    
    memset(dist, -1, sizeof(dist));
    queue<PII> q;
    
    q.push(start);
    dist[start.x][start.y] = 0;

    while (!q.empty())
    {
    
        PII t = q.front(); q.pop();

        for (int i = 0; i < 4; i ++) // enumeration 4 A direction 
        {
    
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;  //  out 
            if (g[x][y] == '#') continue;  //  obstacle 
            if (dist[x][y] != -1) continue;  //  It has been traversed before 

            dist[x][y] = dist[t.x][t.y] + 1;

            if (end == make_pair(x, y)) return dist[x][y];
            else q.push({
    x, y});
        }
    }

    return -1; // All the reachable points in the maze have been traversed once and have not reached the end , It means that the end point is unreachable 
}

int main()
{
    
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> g[i];

    PII start, end;
    for (int i = 0; i < n; i ++) // Find the start and end points first 
        for (int j = 0; j < m; j ++)
            if (g[i][j] == 'S') start = {
    i, j};
            else if (g[i][j] == 'E') end = {
    i, j};

    int distance = bfs(start, end);

    if (distance == -1) puts("oop!");
    else cout << distance;
    
    return 0;
}