Unweighted graph or grid shortest path problems leverage BFS becuase the first visit to a node yields the minimum step count, and iterative queue-based traversal avoids stack overflow risks inherent to deep DFS calls.

8-Puzzle Solver

The 8-puzzle can be modeled as a state space where each arrangement is a node, and swaps of the blank tile (represented by 'x') with adjacent tiles form edges. Use a string to encode each 3x3 state compactly.

import java.util.*;

public class EightPuzzleSolver {
    private static void shiftCharacters(char[] state, int pos1, int pos2) {
        char placeholder = state[pos1];
        state[pos1] = state[pos2];
        state[pos2] = placeholder;
    }

    private static int computeMinSteps(String initial, String target) {
        Map<String, Integer> stepTracker = new HashMap<>();
        Queue<String> stateQueue = new LinkedList<>();
        
        stateQueue.offer(initial);
        stepTracker.put(initial, 0);
        
        int[] directionOffsetsX = {-1, 1, 0, 0};
        int[] directionOffsetsY = {0, 0, 1, -1};
        
        while (!stateQueue.isEmpty()) {
            String current = stateQueue.poll();
            int blankIndex = current.indexOf('x');
            int gridX = blankIndex / 3;
            int gridY = blankIndex % 3;
            
            if (current.equals(target)) return stepTracker.get(current);
            
            for (int d = 0; d < 4; d++) {
                int newX = gridX + directionOffsetsX[d];
                int newY = gridY + directionOffsetsY[d];
                if (newX >= 0 && newX < 3 && newY >= 0 && newY < 3) {
                    char[] currentStateArr = current.toCharArray();
                    shiftCharacters(currentStateArr, blankIndex, newX * 3 + newY);
                    String nextState = new String(currentStateArr);
                    
                    if (!stepTracker.containsKey(nextState)) {
                        stepTracker.put(nextState, stepTracker.get(current) + 1);
                        stateQueue.offer(nextState);
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner inputReader = new Scanner(System.in);
        StringBuilder startState = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            startState.append(inputReader.next());
        }
        String goalState = "12345678x";
        System.out.println(computeMinSteps(startState.toString(), goalState));
    }
}

Flood Fill for Connected Component Counting

Flood Fill efficiently identifies all connected cells in linear time relative to the grid size. It works with 4-directional or 8-directional adjacency, depending on requirements.

Pond Counting (8-Directional Adjacency)

Count connected 'W' cells (water) using 8-directoinal checks to include diagonal neighbors.

import java.io.*;

class GridPoint {
    int row;
    int col;
    GridPoint(int r, int c) {
        row = r;
        col = c;
    }
}

public class PondCounter {
    private static final int MAX_GRID = 1010;
    private static final int QUEUE_SIZE = MAX_GRID * MAX_GRID;
    private static int rows, cols;
    private static char[][] terrain = new char[MAX_GRID][MAX_GRID];
    private static boolean[][] visited = new boolean[MAX_GRID][MAX_GRID];
    private static GridPoint[] bfsQueue = new GridPoint[QUEUE_SIZE];

    private static void fillPond(int startR, int startC) {
        int queueHead = 0, queueTail = -1;
        bfsQueue[++queueTail] = new GridPoint(startR, startC);
        visited[startR][startC] = true;
        
        while (queueHead <= queueTail) {
            GridPoint current = bfsQueue[queueHead++];
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 && dc == 0) continue;
                    int nr = current.row + dr;
                    int nc = current.col + dc;
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                    if (terrain[nr][nc] == '.' || visited[nr][nc]) continue;
                    bfsQueue[++queueTail] = new GridPoint(nr, nc);
                    visited[nr][nc] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] dimensions = br.readLine().split(" ");
        rows = Integer.parseInt(dimensions[0]);
        cols = Integer.parseInt(dimensions[1]);
        
        for (int i = 0; i < rows; i++) {
            String line = br.readLine();
            for (int j = 0; j < cols; j++) {
                terrain[i][j] = line.charAt(j);
            }
        }
        
        int pondCount = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (terrain[i][j] == 'W' && !visited[i][j]) {
                    fillPond(i, j);
                    pondCount++;
                }
            }
        }
        System.out.println(pondCount);
    }
}

Castle Room Analysis (Wall Encoding with Bitmask)

Each castle cell uses a 4-bit integer to encode walls (west, north, east, south as bits 0-3). BFS calculates room count and largest room area.

import java.util.*;

class RoomPoint {
    int x;
    int y;
    RoomPoint(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class CastleAnalyzer {
    private static final int MAX_SIZE = 60;
    private static final int MAX_QUEUE = MAX_SIZE * MAX_SIZE;
    private static int castleRows, castleCols;
    private static int[][] wallGrid = new int[MAX_SIZE][MAX_SIZE];
    private static RoomPoint[] roomQueue = new RoomPoint[MAX_QUEUE];
    private static boolean[][] explored = new boolean[MAX_SIZE][MAX_SIZE];

    private static int exploreRoom(int startX, int startY) {
        int head = 0, tail = -1;
        int[] dirX = {0, -1, 0, 1}; // west, north, east, south
        int[] dirY = {-1, 0, 1, 0};
        int roomArea = 0;
        
        roomQueue[++tail] = new RoomPoint(startX, startY);
        explored[startX][startY] = true;
        
        while (head <= tail) {
            RoomPoint current = roomQueue[head++];
            roomArea++;
            for (int dir = 0; dir < 4; dir++) {
                int nx = current.x + dirX[dir];
                int ny = current.y + dirY[dir];
                if (nx < 0 || ny < 0 || nx >= castleRows || ny >= castleCols) continue;
                if (explored[nx][ny]) continue;
                if ((wallGrid[current.x][current.y] >> dir & 1) == 1) continue;
                roomQueue[++tail] = new RoomPoint(nx, ny);
                explored[nx][ny] = true;
            }
        }
        return roomArea;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        castleRows = sc.nextInt();
        castleCols = sc.nextInt();
        for (int i = 0; i < castleRows; i++) {
            for (int j = 0; j < castleCols; j++) {
                wallGrid[i][j] = sc.nextInt();
            }
        }
        
        int totalRooms = 0;
        int maxArea = 0;
        for (int i = 0; i < castleRows; i++) {
            for (int j = 0; j < castleCols; j++) {
                if (!explored[i][j]) {
                    totalRooms++;
                    maxArea = Math.max(maxArea, exploreRoom(i, j));
                }
            }
        }
        System.out.println(totalRooms);
        System.out.println(maxArea);
    }
}

Mountain Peak and Valley Detection

Classify 8-directional connected regions as peaks (no adjacent higher cells) or valeys (no adjacent lower cells).

import java.util.*;

class TerrainPoint {
    int r;
    int c;
    TerrainPoint(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class MountainValleyCounter {
    private static final int MAX_N = 1010;
    private static final int QUEUE_CAP = MAX_N * MAX_N;
    private static int gridSize;
    private static int[][] heightMap = new int[MAX_N][MAX_N];
    private static boolean[][] checked = new boolean[MAX_N][MAX_N];
    private static TerrainPoint[] terrainQueue = new TerrainPoint[QUEUE_CAP];
    private static boolean hasTallerNeighbor, hasShorterNeighbor;

    private static void scanRegion(int startR, int startC) {
        int head = 0, tail = -1;
        terrainQueue[++tail] = new TerrainPoint(startR, startC);
        checked[startR][startC] = true;
        int regionHeight = heightMap[startR][startC];
        
        while (head <= tail) {
            TerrainPoint current = terrainQueue[head++];
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 && dc == 0) continue;
                    int nr = current.r + dr;
                    int nc = current.c + dc;
                    if (nr < 0 || nr >= gridSize || nc < 0 || nc >= gridSize) continue;
                    
                    if (heightMap[nr][nc] != regionHeight) {
                        if (heightMap[nr][nc] > regionHeight) hasTallerNeighbor = true;
                        else hasShorterNeighbor = true;
                    } else if (!checked[nr][nc]) {
                        checked[nr][nc] = true;
                        terrainQueue[++tail] = new TerrainPoint(nr, nc);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        gridSize = sc.nextInt();
        for (int i = 0; i < gridSize; i++) {
            for (int j = 0; j < gridSize; j++) {
                heightMap[i][j] = sc.nextInt();
            }
        }
        
        int peakCount = 0, valleyCount = 0;
        for (int i = 0; i < gridSize; i++) {
            for (int j = 0; j < gridSize; j++) {
                if (!checked[i][j]) {
                    hasTallerNeighbor = false;
                    hasShorterNeighbor = false;
                    scanRegion(i, j);
                    if (!hasShorterNeighbor) valleyCount++;
                    if (!hasTallerNeighbor) peakCount++;
                }
            }
        }
        System.out.println(peakCount + " " + valleyCount);
    }
}

Path Reconstructing Maze Solver

Reverse BFS from destination to source simplifies path reconstruction without extra storage for steps.

import java.io.*;

class MazePoint {
    int x;
    int y;
    MazePoint(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class MazePathFinder {
    private static final int MAX_MAZE = 1010;
    private static final int MAX_Q = MAX_MAZE * MAX_MAZE;
    private static int mazeDim;
    private static int[][] maze = new int[MAX_MAZE][MAX_MAZE];
    private static MazePoint[] pathQueue = new MazePoint[MAX_Q];
    private static MazePoint[][] prevPoint = new MazePoint[MAX_MAZE][MAX_MAZE];

    private static void reverseBfs(int endX, int endY) {
        int head = 0, tail = -1;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        
        pathQueue[++tail] = new MazePoint(endX, endY);
        prevPoint[endX][endY] = new MazePoint(endX, endY);
        
        while (head <= tail) {
            MazePoint current = pathQueue[head++];
            for (int d = 0; d < 4; d++) {
                int nx = current.x + dx[d];
                int ny = current.y + dy[d];
                if (nx < 0 || ny < 0 || nx >= mazeDim || ny >= mazeDim) continue;
                if (maze[nx][ny] == 1) continue;
                if (prevPoint[nx][ny] != null) continue;
                
                prevPoint[nx][ny] = current;
                pathQueue[++tail] = new MazePoint(nx, ny);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        mazeDim = Integer.parseInt(br.readLine());
        for (int i = 0; i < mazeDim; i++) {
            String[] row = br.readLine().split(" ");
            for (int j = 0; j < mazeDim; j++) {
                maze[i][j] = Integer.parseInt(row[j]);
            }
        }
        
        reverseBfs(mazeDim - 1, mazeDim - 1);
        MazePoint currentPos = new MazePoint(0, 0);
        while (true) {
            System.out.println(currentPos.x + " " + currentPos.y);
            if (currentPos.x == mazeDim - 1 && currentPos.y == mazeDim - 1) break;
            currentPos = prevPoint[currentPos.x][currentPos.y];
        }
    }
}

Knight's Shortest Path

Model knight moves (L-shaped, 8 directions) in a BFS to find minimum steps from start 'K' to target 'H'.

import java.io.*;

class KnightPos {
    int x;
    int y;
    KnightPos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class KnightPath {
    private static final int MAX_BOARD = 200;
    private static final int MAX_Q = MAX_BOARD * MAX_BOARD;
    private static int boardRows, boardCols;
    private static char[][] board = new char[MAX_BOARD][MAX_BOARD];
    private static KnightPos[] knightQueue = new KnightPos[MAX_Q];
    private static int[][] moveCount = new int[MAX_BOARD][MAX_BOARD];

    private static int findMinMoves(int startX, int startY) {
        int head = 0, tail = -1;
        int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
        int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
        
        knightQueue[++tail] = new KnightPos(startX, startY);
        moveCount[startX][startY] = 0;
        
        while (head <= tail) {
            KnightPos current = knightQueue[head++];
            for (int d = 0; d < 8; d++) {
                int nx = current.x + dx[d];
                int ny = current.y + dy[d];
                if (nx < 0 || ny < 0 || nx >= boardRows || ny >= boardCols) continue;
                if (moveCount[nx][ny] != -1) continue;
                if (board[nx][ny] == '*') continue;
                if (board[nx][ny] == 'H') return moveCount[current.x][current.y] + 1;
                
                moveCount[nx][ny] = moveCount[current.x][current.y] + 1;
                knightQueue[++tail] = new KnightPos(nx, ny);
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] dims = br.readLine().split(" ");
        boardCols = Integer.parseInt(dims[0]);
        boardRows = Integer.parseInt(dims[1]);
        
        for (int i = 0; i < boardRows; i++) {
            String line = br.readLine();
            for (int j = 0; j < boardCols; j++) {
                board[i][j] = line.charAt(j);
                moveCount[i][j] = -1;
            }
        }
        
        for (int i = 0; i < boardRows; i++) {
            for (int j = 0; j < boardCols; j++) {
                if (board[i][j] == 'K') {
                    System.out.println(findMinMoves(i, j));
                }
            }
        }
    }
}

One-Dimensional Shortest Path (Cow Chase)

Model positions as nodes, with edges for +1, -1, and *2 moves. BFS ensures minimum steps are found.

import java.util.*;

public class CowChase {
    private static final int MAX_POS = 200010;
    private static int startPos, targetPos;
    private static int[] stepTracker = new int[MAX_POS];
    private static int[] posQueue = new int[MAX_POS];

    private static int calculateSteps() {
        Arrays.fill(stepTracker, -1);
        int head = 0, tail = -1;
        posQueue[++tail] = startPos;
        stepTracker[startPos] = 0;
        
        while (head <= tail) {
            int current = posQueue[head++];
            if (current == targetPos) return stepTracker[current];
            
            if (current - 1 >= 0 && stepTracker[current - 1] == -1) {
                stepTracker[current - 1] = stepTracker[current] + 1;
                posQueue[++tail] = current - 1;
            }
            if (current + 1 < MAX_POS && stepTracker[current + 1] == -1) {
                stepTracker[current + 1] = stepTracker[current] + 1;
                posQueue[++tail] = current + 1;
            }
            if (current * 2 < MAX_POS && stepTracker[current * 2] == -1) {
                stepTracker[current * 2] = stepTracker[current] + 1;
                posQueue[++tail] = current * 2;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        startPos = sc.nextInt();
        targetPos = sc.nextInt();
        System.out.println(calculateSteps());
    }
}