Advertisement
Guest User

Don't Get Volunteered!

a guest
Oct 14th, 2018
529
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.32 KB | None | 0 0
  1. package com.company;
  2.  
  3. import java.util.HashSet;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  6.  
  7. public class Main {
  8.  
  9.     static int[][] gridArr = {{0, 1, 2, 3, 4, 5, 6, 7},
  10.             {8, 9, 10, 11, 12, 13, 14, 15},
  11.             {16, 17, 18, 19, 20, 21, 22, 23},
  12.             {24, 25, 26, 27, 28, 29, 30, 31},
  13.             {32, 33, 34, 35, 36, 37, 38, 39},
  14.             {40, 41, 42, 43, 44, 45, 46, 47},
  15.             {48, 49, 50, 51, 52, 53, 54, 55},
  16.             {56, 57, 58, 59, 60, 61, 62, 63}};
  17.  
  18.  
  19.     static Grid grid = new Grid(gridArr);
  20.  
  21.     public static void main(String[] args) {
  22.  
  23.  
  24.         System.out.println(findShortestKnightPath(8, 14));
  25.     }
  26.  
  27.     public static int findShortestKnightPath(int src, int dest) {
  28.         if (src == dest)
  29.             return 0;
  30.  
  31.         int[][] offset = {{-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}};
  32.         int currentMoves = 0;
  33.  
  34.         HashSet<Integer> visitedSpaces = new HashSet<>();
  35.         Queue<int[]> moveQueue = new LinkedList<>();
  36.  
  37.         //queue holds location and number of moves
  38.         int[] move = {src, 0};
  39.         moveQueue.add(move);
  40.  
  41.         while (!moveQueue.isEmpty()) {
  42.             int[] queuePoll = moveQueue.poll();
  43.             int current = queuePoll[0];
  44.             currentMoves = queuePoll[1];
  45.             currentMoves++;
  46.  
  47.             visitedSpaces.add(current);
  48.  
  49.             int[] currentCoords = grid.getCoords(current);
  50.  
  51.             for (int i = 0; i < grid.gridSize(); i++) {
  52.                 int newX = currentCoords[0] + offset[i][0];
  53.                 int newY = currentCoords[1] + offset[i][1];
  54.                 int newLocation = 0;
  55.                 if (grid.isWithinGrid(newX, newY))
  56.                     newLocation = grid.getLocation(newX, newY);
  57.  
  58.                 if (newLocation == dest) {
  59.                     return currentMoves;
  60.                 }
  61.  
  62.                 if (!visitedSpaces.contains(newLocation)) {
  63.                     int[] queueArr = {newLocation, currentMoves};
  64.                     moveQueue.add(queueArr);
  65.                 }
  66.                 visitedSpaces.add(newLocation);
  67.             }
  68.         }
  69.  
  70.         return currentMoves;
  71.     }
  72. }
  73.  
  74. class Grid {
  75.     int[][] gArr;
  76.  
  77.     public Grid(int[][] gArr) {
  78.         this.gArr = gArr;
  79.     }
  80.  
  81.  
  82.     //gets coords for a point with data that equals location
  83.     public int[] getCoords(int location) {
  84.         //REMINDER: Array looks like: {x, y}
  85.  
  86.         int y = -1;
  87.         int x = location % gArr.length;
  88.         int[] coords = {-1, -1};
  89.  
  90.         //Checks each row for location, i corresponds to each y value
  91.         for (int i = 0; i < gArr.length; i++) {
  92.             if (gArr[i][0] <= location && (gArr[i][0] + 7) >= location)
  93.                 y = i;
  94.         }
  95.  
  96.         //if the value exists, fill the array.
  97.         if (y != -1) {
  98.             coords[0] = x;
  99.             coords[1] = y;
  100.         }
  101.  
  102.         return coords;
  103.     }
  104.  
  105.  
  106.     public int getLocation(int x, int y) {
  107.         return gArr[y][x];
  108.     }
  109.  
  110.  
  111.     //A method to check whether values will be inside the grid
  112.     public boolean isWithinGrid(int x, int y) {
  113.         if (x >= 0 && y >= 0 && x < gArr.length && y < gArr.length) {
  114.             return true;
  115.         }
  116.         return false;
  117.     }
  118.  
  119.     public int gridSize() {
  120.         return gArr.length;
  121.     }
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement