• + 0 comments
    Java 8 Solution with comments, all code credits go to Artemis https://interviewnoodle.com/hackerrank-castle-on-the-grid-problem-solution-6314a877974d
    public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) {       
    				// We will assume the grid is filled and not empty
            // 1. Create a character matrix representing the SQUARE grid.
            int gridSize = grid.size();
            char[][] charGrid = new char[gridSize][gridSize];
            for (int i = 0; i < gridSize; i++) {
                for (int j = 0; j < gridSize; j++) {
                    charGrid[i][j] = grid.get(i).charAt(j);
                }
            }
    
    // 2. Implement BFS w/ a Queue. Point objects will be used to track valid cells.
            Queue<Point> queue = new LinkedList<>();
            // Create a "steps" matrix representing the steps to get to a cell in the grid.
            int[][] steps = new int[gridSize][gridSize];
            // Keep track of cells visited to avoid adding them to the Queue.
            boolean[][] visited = new boolean[gridSize][gridSize];
            // Add the starting point to the queue to start BFS.
            queue.add(new Point(startX, startY));
            visited[startX][startY] = true;
            
            while (!queue.isEmpty()) {
                Point current = queue.poll();
                // 3. We can move in 4 directions: Up (0), Right (1), Down (2), and Left (3).
                //    To represent these directions, refer to xMove and yMove.
                //    We will be adding to our queue the cells of each valid step in each 
                //    direction of our current cell.
                for (int i = 0; i < 4; i++) {
                    // Used to explore the "adjacent" cells a certain valid distance from 
                    // the current cell in each valid direction. 
                    int distance = 1;
                    // Check if the cell we are trying to "move" into is a valid cell.
                    // A valid cell is a cell that is not an obstacle (X), and within bounds.
                    while (isSafe(gridSize, current.x + xMove[i]*distance, current.y + 
                    yMove[i]*distance, charGrid) && !visited[current.x + xMove[i]*distance]
                    [current.y + yMove[i]*distance]) {
                        // Record the Point coordinates to be added into the queue.
                        int nextX = current.x + xMove[i]*distance;
                        int nextY = current.y + yMove[i]*distance;
                        visited[nextX][nextY] = true;
                        queue.add(new Point(nextX, nextY));
                        // Keep track of the "steps" taken to get to a cell.
                        steps[nextX][nextY] = steps[current.x][current.y] +1;
                        // Case where the point "adjacent" to current is the goal.
                        if (nextX == goalX && nextY == goalY) {
                            System.out.println(steps[nextX][nextY]);
                            return steps[nextX][nextY];
                        }
                        distance++;
                    }
                }
            }
            
            // By default, return -1, indicating that the grid was not valid.
            return -1;
        }
    		
     // Helper arrays used to define directions.
     // To move up (index 0): xMove is -1, yMove is 0.
     // To move right (index 1): xMove is 0, yMove is 1.
     // To move down (index 2): xMove is 1, yMove is 0.
     // To move left (index 3): xMove is 0, yMove is -1.
        private static int[] xMove = {-1, 0, 1, 0};
        private static int[] yMove = { 0, 1, 0, -1};
        
        // Private helper class to check if a step/move to a cell is valid in the grid.
        private static boolean isSafe (int gridSize, int x, int y, char[][] charGrid) {
            return (x >= 0 && 
                    y >= 0 && 
                    x < gridSize && 
                    y < gridSize && 
                    charGrid[x][y] == '.');
        }
    }
    
    // Private helper class used to instantiate "Point" objects
    // A "Point" is used in the queue used to store valid moves from
    // a current "Point"
    class Point {
        public int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }