Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class MazeSolver {
- static class P implements Comparable<P> {
- public int r, c;
- public int dist;
- public P prev;
- public P(int row, int col) {
- r = row;
- c = col;
- dist = 0;
- prev = null;
- }
- public P extend(int row, int col, int dist) {
- P ret = new P(row, col);
- ret.dist = this.dist + dist;
- ret.prev = this;
- return ret;
- }
- public int compareTo(P other) {
- // if this < other, return negative
- // if this == other, return 0
- // if this > other, return positive
- return Integer.compare(this.dist, other.dist);
- }
- public boolean equals(Object other1) {
- P other = (P) other1;
- return this.row == other.row && this.col == other.col;
- }
- public int hashCode() {
- return this.row * 137 + this.col;
- }
- }
- public static void main(String[] argv) throws IOException {
- Scanner sc = new Scanner(new File("data.dat"));
- int rows = sc.nextInt(), cols = sc.nextInt(); sc.nextLine();
- char[][] grid = new char[rows][];
- P start = null, end = null;
- for (int i = 0; i < rows; i++) {
- grid[i] = sc.nextLine().toCharArray();
- for (int j = 0; j < cols; j++) {
- if (grid[i][j] == '@') {
- start = new P(i, j);
- }
- if (grid[i][j] == '$') {
- end = new P(i, j);
- }
- }
- }
- HashSet<P> visited = new HashSet<>();
- PriorityQueue<P> Q = new PriorityQueue<>();
- Q.add(start);
- while (!Q.isEmpty()) {
- P cur = Q.remove();
- if (visited.contains(cur)) continue;
- visited.add(cur);
- if (cur.equals(end)) {
- end = cur;
- break;
- }
- for (int dr = -1; dr <= 1; dr++) {
- for (int dc = -1; dc <= 1; dc++) {
- // both r and c in [-1, 1]
- if (Math.abs(dr) == Math.abs(dc)) {
- continue;
- }
- int nr = cur.r + dr, nc = cur.c + dc;
- if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
- int dist = 1;
- if (grid[nr][nc] == '#') continue;
- if (grid[nr][nc] == '^') dist = 5;
- Q.add(cur.extend(cur.r + dr, cur.c + dc), dist);
- }
- }
- }
- // end contains the whole chain and total distance
- // example: if you want in order
- ArrayList<P> path = new ArrayList<P>();
- P cur = end;
- while (cur != null) {
- path.add(cur); // added backwards
- cur = cur.prev;
- }
- Collections.reverse(path);
- // if you don't care, instead of adding to arraylist, work with it
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement