Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Main {
- public static int lyhinReitti(int[][] kartta) {
- Node[][] nodes = new Node[kartta.length + 1][kartta[0].length + 1];
- Node alku = new Node(false);
- for (int x = 1; x < kartta.length - 1; x++) {
- for (int y = 1; y < kartta[0].length - 1; y++) {
- if (kartta[x][y] == 0 || kartta[x][y] == 2) {
- Node newNode = new Node(false);
- if (kartta[x][y] == 2) {
- alku = newNode;
- }
- nodes[x][y] = newNode;
- } else if (kartta[x][y] == 3) {
- nodes[x][y] = new Node(true);
- }
- }
- }
- for (int x = 1; x < kartta.length - 1; x++) {
- for (int y = 1; y < kartta[0].length - 1; y++) {
- if (nodes[x][y] != null) {
- if (nodes[x - 1][y] != null) {
- nodes[x][y].routes.add(nodes[x - 1][y]);
- }
- if (nodes[x + 1][y] != null) {
- nodes[x][y].routes.add(nodes[x + 1][y]);
- }
- if (nodes[x][y - 1] != null) {
- nodes[x][y].routes.add(nodes[x][y - 1]);
- }
- if (nodes[x][y + 1] != null) {
- nodes[x][y].routes.add(nodes[x][y + 1]);
- }
- }
- }
- }
- ArrayDeque<Node> current = new ArrayDeque<>();
- current.add(alku);
- while (!current.isEmpty()) {
- Node currentNode = current.poll();
- if (currentNode.goal) {
- return currentNode.pituus;
- }
- currentNode.visited = true;
- for (Node nextNode : currentNode.routes) {
- if (!nextNode.visited) {
- nextNode.pituus = currentNode.pituus + 1;
- current.add(nextNode);
- }
- }
- }
- return -1;
- }
- public static void main(String[] args) {
- int[][] kartta = {{1, 1, 1, 1, 1, 1, 1, 1},
- {1, 0, 3, 1, 0, 0, 0, 1},
- {1, 0, 1, 1, 0, 1, 0, 1},
- {1, 0, 0, 0, 0, 2, 0, 1},
- {1, 1, 1, 1, 1, 1, 1, 1}};
- System.out.println(lyhinReitti(kartta));
- }
- }
- ---------------------------------------------
- import java.util.ArrayList;
- public class Node {
- ArrayList<Node> routes;
- boolean visited;
- boolean goal;
- int pituus;
- public Node(boolean goal) {
- this.routes = new ArrayList<>();
- this.visited = false;
- this.goal = goal;
- this.pituus = 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement