fork(4) download 
  1. import java.util.*;
  2.  
  3. class Ideone {
  4. 	public static void main (String[] args) {
  5. 		char[][] board = {{'0', '2', '1', '1', '1'},
  6. 		                  {'0', '1', '0', '0', '1'},
  7. 		                  {'0', '0', '0', '0', '1'},
  8. 		                  {'0', '0', 'A', '0', '1'},
  9. 		                  {'1', '1', 'a', '1', '1'},
  10. 		                  {'1', 'b', '0', '0', 'B'},
  11. 		                  {'1', '1', '0', '0', '1'},
  12. 		                  {'0', '1', '0', '0', '3'}};
  13. 		System.out.println(pathToString(solve(board)));
  14. 	}
  15. 	private static final class Coord {
  16. 		final int y, x;
  17. 		Coord(int y, int x) {
  18. 			this.y = y;
  19. 			this.x = x;
  20. 		}
  21. 		@Override public String toString() {
  22. 			return String.valueOf(this.y).concat(String.valueOf(this.x));
  23. 		}
  24. 	}
  25. 	private static String pathToString(Iterable<Coord> path) {
  26. 		StringJoiner joiner = new StringJoiner("->");
  27. 		for (Coord coord : path)
  28. 			joiner.add(coord.toString());
  29. 		return joiner.toString();
  30. 	}
  31. 	private static List<Coord> solve(char[][] board) {
  32. 		List<Coord> shortestPathToGoal = new ArrayList<>();
  33. 		for (int y = 0; y < board.length; y++)
  34. 			for (int x = 0; x < board[y].length; x++)
  35. 				if (board[y][x] == '2'/*Start*/)
  36. 					walk(board, y, x, 0, initVisited(board), new ArrayDeque<>(), shortestPathToGoal);
  37. 		return shortestPathToGoal;
  38. 	}
  39. 	private static void walk(char[][] board, int y, int x, int keyRing, boolean[][] visited,
  40. 	                         Deque<Coord> path, List<Coord> shortestPathToGoal) {
  41. 		if (y < 0 || y >= board.length || x < 0 || x >= board[y].length || visited[y][x])
  42. 			return; // outside board or already visited
  43. 		char point = board[y][x];
  44. 		if (point == '0'/*Water*/)
  45. 			return; // cannot walk on water
  46. 		if (point == '3'/*Goal*/) {
  47. 			shortestPathToGoal.clear();
  48. 			shortestPathToGoal.addAll(path);
  49. 			shortestPathToGoal.add(new Coord(y, x));
  50. 			return; // return to look for alternate shorter path
  51. 		}
  52. 		if (! shortestPathToGoal.isEmpty() && path.size() + 2 >= shortestPathToGoal.size())
  53. 			return; // shorter (or equal) path already found
  54. 		if (point >= 'A' && point <= 'Z') { // Door
  55. 			if ((keyRing & (1 << (point - 'A'))) == 0)
  56. 				return; // missing key
  57. 		} else if (point >= 'a' && point <= 'z') { // Key
  58. 			if ((keyRing & (1 << (point - 'a'))) == 0) {
  59. 				keyRing |= (1 << (point - 'a')); // add key to keyring
  60. 				visited = initVisited(board); // may now revisit previous steps
  61. 			}
  62. 		}
  63. 		visited[y][x] = true;
  64. 		path.addLast(new Coord(y, x));
  65. 		walk(board, y    , x + 1, keyRing, visited, path, shortestPathToGoal); // right
  66. 		walk(board, y + 1, x    , keyRing, visited, path, shortestPathToGoal); // down
  67. 		walk(board, y    , x - 1, keyRing, visited, path, shortestPathToGoal); // left
  68. 		walk(board, y - 1, x    , keyRing, visited, path, shortestPathToGoal); // up
  69. 		path.removeLast();
  70. 		visited[y][x] = false;
  71. 	}
  72. 	private static boolean[][] initVisited(char[][] board) {
  73. 		boolean[][] visited = new boolean[board.length][];
  74. 		for (int y = 0; y < board.length; y++)
  75. 			visited[y] = new boolean[board[y].length];
  76. 		return visited;
  77. 	}
  78. }
Success #stdin #stdout 0.04s 712192KB
comments (?)
stdin 
Standard input is empty
stdout 
01->02->03->04->14->24->34->44->43->42->41->51->41->42->43->44->54->64->74
https://ideone.com/CWwNwE
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!