Advertisement
Guest User

Untitled

a guest
Mar 21st, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.79 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5. public static int lyhinReitti(int[][] kartta) {
  6. Node[][] nodes = new Node[kartta.length + 1][kartta[0].length + 1];
  7. Node alku = new Node(false);
  8.  
  9. for (int x = 1; x < kartta.length - 1; x++) {
  10. for (int y = 1; y < kartta[0].length - 1; y++) {
  11. if (kartta[x][y] == 0 || kartta[x][y] == 2) {
  12. Node newNode = new Node(false);
  13.  
  14. if (kartta[x][y] == 2) {
  15. alku = newNode;
  16. }
  17.  
  18.  
  19. nodes[x][y] = newNode;
  20. } else if (kartta[x][y] == 3) {
  21. nodes[x][y] = new Node(true);
  22. }
  23. }
  24. }
  25.  
  26. for (int x = 1; x < kartta.length - 1; x++) {
  27. for (int y = 1; y < kartta[0].length - 1; y++) {
  28. if (nodes[x][y] != null) {
  29. if (nodes[x - 1][y] != null) {
  30. nodes[x][y].routes.add(nodes[x - 1][y]);
  31. }
  32.  
  33. if (nodes[x + 1][y] != null) {
  34. nodes[x][y].routes.add(nodes[x + 1][y]);
  35. }
  36.  
  37. if (nodes[x][y - 1] != null) {
  38. nodes[x][y].routes.add(nodes[x][y - 1]);
  39. }
  40.  
  41. if (nodes[x][y + 1] != null) {
  42. nodes[x][y].routes.add(nodes[x][y + 1]);
  43. }
  44. }
  45. }
  46. }
  47.  
  48. ArrayDeque<Node> current = new ArrayDeque<>();
  49. current.add(alku);
  50.  
  51. while (!current.isEmpty()) {
  52. Node currentNode = current.poll();
  53.  
  54. if (currentNode.goal) {
  55. return currentNode.pituus;
  56. }
  57.  
  58. currentNode.visited = true;
  59.  
  60. for (Node nextNode : currentNode.routes) {
  61. if (!nextNode.visited) {
  62. nextNode.pituus = currentNode.pituus + 1;
  63. current.add(nextNode);
  64. }
  65. }
  66. }
  67.  
  68. return -1;
  69. }
  70.  
  71. public static void main(String[] args) {
  72. int[][] kartta = {{1, 1, 1, 1, 1, 1, 1, 1},
  73. {1, 0, 3, 1, 0, 0, 0, 1},
  74. {1, 0, 1, 1, 0, 1, 0, 1},
  75. {1, 0, 0, 0, 0, 2, 0, 1},
  76. {1, 1, 1, 1, 1, 1, 1, 1}};
  77. System.out.println(lyhinReitti(kartta));
  78. }
  79. }
  80.  
  81.  
  82.  
  83. ---------------------------------------------
  84.  
  85.  
  86.  
  87. import java.util.ArrayList;
  88.  
  89. public class Node {
  90.  
  91. ArrayList<Node> routes;
  92. boolean visited;
  93. boolean goal;
  94. int pituus;
  95.  
  96. public Node(boolean goal) {
  97. this.routes = new ArrayList<>();
  98. this.visited = false;
  99. this.goal = goal;
  100. this.pituus = 0;
  101. }
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement