Depth-First Search and Grids

Explore a maze with one hand on the wall

Depth-first search (DFS) follows one path as far as it can, then backs up and tries the next branch. Recursion does the backing up for us:

import java.util.ArrayList;

public class Main {
    static ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
    static boolean[] seen;

    static void dfs(int node, ArrayList<Integer> group) {
        seen[node] = true;
        group.add(node);
        for (int next : g.get(node)) {
            if (!seen[next]) dfs(next, group);
        }
    }

    public static void main(String[] args) {
        int n = 7;
        for (int i = 0; i <= n; i++) g.add(new ArrayList<Integer>());
        int[][] links = {{1, 2}, {2, 3}, {4, 5}, {6, 7}, {7, 4}};
        for (int[] e : links) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }

        seen = new boolean[n + 1];
        int groups = 0;
        for (int person = 1; person <= n; person++) {
            if (!seen[person]) {                 // a new, unexplored group
                ArrayList<Integer> group = new ArrayList<Integer>();
                dfs(person, group);
                groups++;
                System.out.println("group " + groups + ": " + group);
            }
        }
    }
}

Output

group 1: [1, 2, 3]
group 2: [4, 5, 7, 6]

Each separate piece of a graph is called a connected component. Starting a DFS from every unvisited node counts them – still O(n + m) in total.

A grid is a graph too

A maze or map drawn as a grid of characters is a graph: each cell is a node, and its up/down/left/right neighbours are its edges. Use two small arrays for the four directions:

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        String[] maze = {
            "S.#.",
            ".##.",
            "...E"
        };
        int rows = maze.length, cols = maze[0].length();
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) java.util.Arrays.fill(row, -1);

        ArrayDeque<int[]> queue = new ArrayDeque<int[]>();
        dist[0][0] = 0;
        queue.offer(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int d = 0; d < 4; d++) {
                int r = cell[0] + dr[d], c = cell[1] + dc[d];
                if (r < 0 || c < 0 || r >= rows || c >= cols) continue;   // off the map
                if (maze[r].charAt(c) == '#' || dist[r][c] != -1) continue; // wall or seen
                dist[r][c] = dist[cell[0]][cell[1]] + 1;
                queue.offer(new int[]{r, c});
            }
        }
        System.out.println("steps from S to E: " + dist[2][3]);
    }
}

Output

steps from S to E: 5

Tip: Deep recursion can overflow the stack on huge graphs. For the sizes in these challenges recursion is fine; for millions of nodes, use BFS or a DFS with your own ArrayDeque stack.