PathFinding.java

PathFinding.java

import java.util.*;


public final class PathFinding {

	static final class State {
		final int ax, ay, bx, by;
		final int hash;
		State(int ax, int ay, int bx, int by) {
			this.ax = ax;
			this.bx = bx;
			this.ay = ay;
			this.by = by;
			assert ax != bx || ay != by: this;
			this.hash = Arrays.hashCode(new int[]{ax, ay, bx, by});
		}
		State(int[] a, int[] b) {
			this(a[0], a[1], b[0], b[1]);
		}
		@Override
		public int hashCode() {
			return hash;
		}
		@Override
		public boolean equals(Object o) {
			State s = (State) o;
			return hash == s.hash && ax == s.ax && bx == s.bx && ay == s.ay && by == s.by;
		}
		@Override
		public String toString() {
			return String.format("{%d,%d}/{%d,%d}", ax, ay, bx, by);
		}
	}

	static final class Count {
		final State s;
		final int count;
		Count(State s, int count) {
			this.s = s;
			this.count = count;
		}
	}

	private static int[] find(String[] set, char x) {
		int[] ret = new int[2];
		for (int i=0; i<set.length; ++i) {
			for (int j=0; j<set[0].length(); ++j) {
				if (set[i].charAt(j) == x) {
					ret[0] = i;
					ret[1] = j;
					return ret;
				}
			}
		}
		throw new AssertionError("not found " + x);
	}

	private static int[] make(int a, int b) {
		int[] ret = new int[2];
		ret[0] = a;
		ret[1] = b;
		return ret;
	}

	private static Collection<Count> findNeighbors(String[] set, Count ct, Set<State> visited) {
		final int row = set.length;
		final int col = set[0].length();

		List<int[]> an = new ArrayList<>();
		an.add(make(ct.s.ax, ct.s.ay));

		for (int r=-1; r<=1; ++r) {
			for (int c=-1; c<=1; ++c) {
				final int x = ct.s.ax + r;
				final int y = ct.s.ay + c;
				if (x >= 0 && x < row && y >= 0 && y < col) {
					if (set[x].charAt(y) != 'X') {
						an.add(make(x, y));
					}
				}
			}
		}

		List<int[]> bn = new ArrayList<>();
		bn.add(make(ct.s.bx, ct.s.by));

		for (int r=-1; r<=1; ++r) {
			for (int c=-1; c<=1; ++c) {
				final int x = ct.s.bx + r;
				final int y = ct.s.by + c;
				if (x >= 0 && x < row && y >= 0 && y < col) {
					if (set[x].charAt(y) != 'X') {
						bn.add(make(x, y));
					}
				}
			}
		}

		final Set<State> lbs = new HashSet<>();

		for (int[] a : an) {
			for (int[] b : bn) {
				if (a[0] == b[0] && a[1] == b[1]) continue;
				State s = new State(a, b);
				if (!visited.contains(s)) {
					lbs.add(s);
				}
			}
		}

		lbs.remove(ct.s);
		lbs.remove(new State(bn.get(0), an.get(0)));

		final List<Count> result = new ArrayList<>();
		for (State s : lbs) {
			result.add(new Count(s, ct.count+1));
		}

		return result;
	}

	public static int minTurns(String[] set) {
		final Set<State> visited = new HashSet<>();

		int[] a = find(set, 'A');
		int[] b = find(set, 'B');


		State start = new State(a, b);
		State end = new State(b, a);

		// System.out.printf("start %s, end %s\n", start, end);

		visited.add(end);

		Deque<Count> q = new ArrayDeque<>();
		q.add(new Count(end, 0));

		while (!q.isEmpty()) {
			Count c = q.removeFirst();
			// System.out.printf("pop %s\n", c.s);

			if (c.s.equals(start)) {
				return c.count;
			}

			for (Count nb : findNeighbors(set, c, visited)) {
				// System.out.printf("\tstate %s, nb %s, count %d, visited %d\n", c.s, nb.s, c.count, visited.size());
				visited.add(nb.s);
				q.add(nb);
			}
		}

		return -1;
	}
}