Discussion on Castle on the Grid Challenge

4 days ago+ 0 comments

My Java 8 solution, passing all test-cases, for a Max Score of 30:

The core idea is to implement a Breadth-First-Search (BFS) of a Queue of Points, expanding the search in all four directions (Up, Down, Left, Right) - and sliding along each direction - till we reach either a boundary or an obstacle ('X'), and add each "unvisited" point into the Queue of Points. And all throughout, we keep track of visited (boolean) & visited (distances) for points visited along the BFS. We keep doing this either till the Queue is EMPTY (in which case we have NOT been able to reach the Goal), or till we reach the Goal Point.

This is guaranteed to give us optimal solution, in O(n^2) time.

Ignore the "vDbg" statements, as those are just for diagnostic / debug purposes, to understand the logic or debug better. You can enable / disable it via the "vDbg" flag. If enabled, it might slow execution time, resulting in failing some test-cases due to TLEs. I

class Result {

    // Only given for Diagnostic / Debug purposes.
    // Enabling this might result in slower execution.
    // Hence, it might fail test-cases with TLEs.
    private static final boolean vDbg = false;
    
    private static class Point {
        int rowIdx, colIdx;

        Point(int rowIdx, int colIdx) {
            this.rowIdx = rowIdx; this.colIdx = colIdx;
        }
        
        @Override
        public String toString() {
            return "(" + rowIdx + "," + colIdx + ")";
        }
    }

    /*
     * Complete the 'minimumMoves' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. STRING_ARRAY grid
     *  2. INTEGER startX
     *  3. INTEGER startY
     *  4. INTEGER goalX
     *  5. INTEGER goalY
     */

    public static int minimumMoves(List<String> grid, 
                      int startX, int startY, int goalX, int goalY) {
        // Write your code here
        int n = grid.size();

        // "visited[i][j]" indicates whether point (i,j) has been visited in BFS
        boolean[][] visited = new boolean[n][n];

        // "numMoves[i][j]" indicates the number of moves it takes to get to point (i,j)
        int[][] numMoves = new int[n][n];

        // Queue of Points, that's populated & de-populated during BFS
        Queue<Point> pointsQ = new ArrayDeque<>();

        // Initialize the Start Conditions for Breadth-First-Search (BFS)
        pointsQ.add(new Point(startX, startY));
        visited[startX][startY] = true;
        numMoves[startX][startY] = 0;

        // Direction Offsets along Rows / Columns
        // We can go four Directions: Up, Down, Left, Right
        int[] dirRowOffset = {1, -1, 0, 0};
        int[] dirColOffset = {0, 0, 1, -1};

        // Perform the Breadth-First-Search (BFS) using the Points Queue.
        while (!pointsQ.isEmpty()) {

            Point bfsPoint = pointsQ.poll();
            int curNumMoves = numMoves[bfsPoint.rowIdx][bfsPoint.colIdx];

            if (vDbg) {
                System.err.println(""); System.err.println("");
                System.err.println("pointsQ.size() = >" + pointsQ.size() + "< | " + 
                                   "bfsPoint = >" + bfsPoint + "< | " + 
                                   "curNumMoves = >" + curNumMoves + "<");
                System.err.println("pointsQ = >" + pointsQ + "<");
            }

            if (bfsPoint.rowIdx == goalX && bfsPoint.colIdx == goalY) {
                if (vDbg) { System.err.println("Success! Reached Goal in >" + 
                                               curNumMoves + "< moves!"); }
                return curNumMoves;
            }

            // Slide in all 4 directions
            for (int dirIdx = 0; dirIdx < 4; dirIdx++) {

                int nextRowIdx = bfsPoint.rowIdx + dirRowOffset[dirIdx];
                int nextColIdx = bfsPoint.colIdx + dirColOffset[dirIdx];

                if (vDbg) { System.err.println("Starting along DIR: " + 
                                               "dirIdx = >" + dirIdx + "< | " + 
                                               "nextRowIdx = >" + nextRowIdx + "< | " + 
                                               "nextColIdx = >" + nextColIdx + "<"); }

                // Slide in the SAME direction until boundary or blocked
                while ( nextRowIdx >= 0 && nextRowIdx < n && 
                        nextColIdx >= 0 && nextColIdx < n && 
                        grid.get(nextRowIdx).charAt(nextColIdx) == '.' ) {

                    if (vDbg) { System.err.println("Sliding along DIR: " + 
                                                   "dirIdx = >" + dirIdx + "< | " + 
                                                   "nextRowIdx = >" + nextRowIdx + "< | " + 
                                                   "nextColIdx = >" + nextColIdx + "< | " + 
                                                   "visited = >" + 
                                                   visited[nextRowIdx][nextColIdx] + "<"); }

                    if (!visited[nextRowIdx][nextColIdx]) {
                        
                        Point nextPoint = new Point(nextRowIdx, nextColIdx);

                        visited[nextRowIdx][nextColIdx] = true;
                        numMoves[nextRowIdx][nextColIdx] = (curNumMoves + 1);
                        pointsQ.add(nextPoint);

                        if (vDbg) { System.err.println("Adding new UNVISITED Point " + 
                                                       nextPoint + " into the Queue, " + 
                                                       "for further BFS."); }

                    }

                    // Slide further in the SAME direction
                    nextRowIdx += dirRowOffset[dirIdx];
                    nextColIdx += dirColOffset[dirIdx];

                }

            }

        }

        return -1;
    }

}

Cookie support is required to access HackerRank