the shortest path problem - mazes

i will make a problemset for this later (maybe)

bfs animation 1

bfs animation 2

the rest of the page will use these as sample inputs. 3 is the number of rows, 6 is the number of columns per row, # is a wall, . is a path, S is the start, E is the end.

sample input 1

3 6
.S#...
.##.#.
....#E

sample input 2

xxxxxxxxxx
3 6
.S#...
.####.
....#E

problem A: output whether you can get from S to E

sample output 1

xxxxxxxxxx
YES

sample output 2

NO

approach:

• n rows, m columns
• grid - 2D array of characters to represent the maze
• find the coordinates of S
• start BFS at S
• if BFS finds E then output YES and exit
• if BFS terminates without finding E then output NO

java solution

xxxxxxxxxx
import java.util.*;
class Solution {
    public static void main(String[]$) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt(), m=in.nextInt();
        in.nextLine(); // required because previous operation did not consume the \n
        char[][] grid = new char[n][];
        for (int r=0; r<n; ++r)
            grid[r] = in.nextLine().toCharArray();
        int sr=0, sc=0; // start coords, initial values don't matter
        for (int r=0; r<n; ++r)
            for (int c=0; c<m; ++c)
                if (grid[r][c]=='S') {
                    sr=r; sc=c; }
        Queue<Integer> qr=new ArrayDeque<>(), qc=new ArrayDeque<>();
        qr.add(sr); qc.add(sc);
        int[] dr = { -1,  0,  1,  0 },
              dc = {  0, -1,  0,  1 };
        while (!qr.isEmpty()) { // note that qr.size()==qc.size() always
            int r=qr.remove(), c=qc.remove();
            if (grid[r][c]=='#') continue;
            else if (grid[r][c]=='E') {
                System.out.print("YES"); return;
            } else grid[r][c] = '#'; // mark as visited
            for (int i=0; i<4; ++i) {
                int nr=r+dr[i], nc=c+dc[i]; // new coordinates
                if (0<=nr&&nr<n && 0<=nc&&nc<m && grid[nr][nc]!='#') {
                    qr.add(nr); qc.add(nc); }
            }
        }
        System.out.print("NO");
    }
}

python solution

xxxxxxxxxx
n, m = map(int, input().split())
grid = [list(input()) for _ in range(n)]
for r in range(n):
    for c in range(m):
        if grid[r][c]=='S':
            sr, sc = r, c
from collections import deque
q = deque() # queue of tuples
q.append((sr,sc))
moves = list(zip([-1,0,1,0],[0,-1,0,1]))
while q:
    r, c = q.popleft()
    if grid[r][c]=='#': continue
    elif grid[r][c]=='E':
        print('YES')
        exit()
    else: grid[r][c] = '#'
    for dr, dc in moves:
        nr, nc = r+dr, c+dc
        if 0<=nr<n and 0<=nc<m and grid[nr][nc]!='#':
            q.append((nr,nc))
print('NO')

c++ solution

xxxxxxxxxx
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    char grid[n][m];
    int sr, sc;
    for (int r=0; r<n; ++r)
        for (int c=0; c<m; ++c) {
            cin >> grid[r][c];
            if (grid[r][c]=='S')
                sr=r, sc=c;
        }
    queue<int> qr, qc;
    qr.push(sr); qc.push(sc);
    int dr[4] = { -1,  0,  1,  0 },
        dc[4] = {  0, -1,  0,  1 };
    while (!qr.empty()) {
        int r=qr.front(), c=qc.front();
        qr.pop(), qc.pop();
        if (grid[r][c]=='#') continue;
        else if (grid[r][c]=='E') {
            cout << "YES"; return 0;
        } else grid[r][c] = '#';
        for (int i=0; i<4; ++i) {
            int nr=r+dr[i], nc=c+dc[i];
            if (0<=nr&&nr<n && 0<=nc&&nc<m && grid[nr][nc]!='#')
                qr.push(nr), qc.push(nc);
        }
    }
    cout << "NO";
}

* none of this code has been tested against rigorous data, if there are problems with it lmk

problem B: output the length of the shortest path from S to E

* you can only move up, down, left, right * -1 if no path

sample output 1

12

sample output 2

-1

in the code for problem A, there's a queue for row and a queue for column. one way to do problem B is to create a third queue for distance - initialize with 0 and push [distance of old node] + 1 for every new node.

practice problem

problem C: output the shortest sequence of moves (up down left right) from S to E

* X if no path

sample output 1

LDDRRRUURRDD

sample output 2

xxxxxxxxxx
X

one way is to make a variable mapping from [NODE] to [whichever node NODE came from]. after the BFS finds E, retrace the path by going through the map, e.g. E came from [a node], [a node] came from [another node], [another node] came from S. from these, you can figure out the steps it took to get from S to E.

in Python and C++, you can map from tuple to tuple or std::pair<int,int> to std::pair<int,int>, respectively. in Java you might want to use the java.awt.Point class or make your own thing to store two ints.