Pacman A*

PacmanAStar.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class PacmanAStar {

    private static int[] pacPos;
    private static int[] foodPos;
    private static int[] dim;
    private static char[][] grid;

    private static Set<Cell> visited;
    private static Queue<Cell> aStartPQueue;

    private static int[][] diffs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        pacPos = new int[] { scan.nextInt(), scan.nextInt() };
        foodPos = new int[] { scan.nextInt(), scan.nextInt() };
        dim = new int[] { scan.nextInt(), scan.nextInt() };

        scan.nextLine();

        grid = new char[dim[0]][dim[1]];

        for (int i = 0; i < dim[0]; i++) {
            String line = scan.nextLine();

            for (int j = 0; j < dim[1]; j++) {
                grid[i][j] = line.charAt(j);
            }
        }

        startAStar();
    }

    private static void startAStar() {

        visited = new HashSet<>();
        aStartPQueue = new PriorityQueue<>();

        Cell source = new Cell(pacPos[0], pacPos[1]);
        Cell dest = new Cell(foodPos[0], foodPos[1]);

        visited.add(source);
        aStartPQueue.add(source);

        while (!aStartPQueue.isEmpty()) {
            Cell current = aStartPQueue.poll();

            if (current.equals(dest)) {
                dest.pred = current.pred;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int r = current.r + diffs[i][0];
                int c = current.c + diffs[i][1];

                if (isSafe(r, c)) {
                    Cell nei = new Cell(r, c);
                    nei.g = current.g + 1;
                    nei.h = manhattanDist(r, c);
                    nei.pred = current;

                    if (!visited.contains(nei)) {
                        visited.add(nei);
                        aStartPQueue.add(nei);
                    }
                }
            }
        }

        List<String> paths = new ArrayList<>();
        Cell cursor = dest;

        while (cursor.getPred() != null) {
            paths.add(cursor.r + " " + cursor.c);
            cursor = cursor.pred;
        }

        Collections.reverse(paths);

        System.out.println(paths.size());
        System.out.println(pacPos[0] + " " + pacPos[1]);

        for (String path : paths) {
            System.out.println(path);
        }
    }

    private static int manhattanDist(int r, int c) {
        return Math.abs(r - foodPos[0]) + Math.abs(c - foodPos[1]);
    }

    private static boolean isSafe(int r, int c) {
        return r >= 0 && c >= 0 && r < dim[0] && c < dim[1] && grid[r][c] != '%';
    }
}

class Cell implements Comparable<Cell> {
    String id;
    int r;
    int c;
    int g;
    int h;
    Cell pred;

    public Cell(int r, int c) {
        this.r = r;
        this.c = c;
        this.id = r + "-" + c;
    }

    @Override
    public int hashCode() {
        return id.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return ((Cell) obj).id.equals(id);
    }

    public int getF() {
        return g + h;
    }

    @Override
    public int compareTo(Cell o) {
        int f = getF();
        int of = o.getF();

        if (f == of) {
            if (c == o.c) {
                return r - o.r;
            }

            return c - o.c;
        }

        return f - of;
    }
}