We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Queues
  4. Castle on the Grid
  5. Discussions

Castle on the Grid

Sort by

recency

|

336 Discussions

|

  • rajivaiyer
     + 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;
    }

}

  • mcyanek
     + 0 comments

    Shouldn't test case 0 expect return value of 4? It expects 3, but i don't see how could it be done in 3 moves. All other test cases are green in my case.

  • chahatchakrawar1
     + 0 comments

    include

    include

    include

    using namespace std;

    struct Node { int x, y, moves; };

    int minimumMoves(vector grid, int startX, int startY, int goalX, int goalY) { int n = grid.size(); vector> visited(n, vector(n, false)); queue q; q.push({startX, startY, 0}); visited[startX][startY] = true;

    int dx[] = {-1, 1, 0, 0}; // up, down
int dy[] = {0, 0, -1, 1}; // left, right

while (!q.empty()) {
    Node curr = q.front();
    q.pop();

    if (curr.x == goalX && curr.y == goalY)
        return curr.moves;

    for (int dir = 0; dir < 4; ++dir) {
        int nx = curr.x;
        int ny = curr.y;
        while (true) {
            nx += dx[dir];
            ny += dy[dir];

            if (nx < 0 || ny < 0 || nx >= n || ny >= n || grid[nx][ny] == 'X')
                break;

            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny, curr.moves + 1});
            }
        }
    }
}
return -1; // should never reach here if input guarantees a path

    }

    int main() { int n; cin >> n; vector grid(n); for (int i = 0; i < n; ++i) cin >> grid[i];

    int startX, startY, goalX, goalY;
cin >> startX >> startY >> goalX >> goalY;

cout << minimumMoves(grid, startX, startY, goalX, goalY) << endl;

        return 0; }

  • otternesstracyn
     + 0 comments

    It would be helpful if the description specified whether or not one MUST go until you hit a wall or the edge (think video game ice grid puzzles) or if the player can optionall stop short (think rook in chess). The name of this gives a hint for those familiar with chess, but I do not think it is obvious from the problem description alone to someone unfamiliar with that game.

  • josephyv
     + 0 comments

    Solution in C using BFS algorithm

    struct steps {
  int x, y, movements;
};

int validPosition(int n, int x, int y) {

  if (x < 0 || x >= n || y < 0 || y >= n)
    return 0;
  return 1;
}

int minimumMoves(int grid_count, char **grid, int startX, int startY, int goalX,
                 int goalY) {
  int ans = 0;
  int MAX_SIZE = (grid_count * grid_count) + 2;
  struct steps *queue = malloc(MAX_SIZE * sizeof(struct steps));
  int back = 0, front = 0;

  struct steps root = {startX, startY, 0};
  queue[back++] = root;
  grid[startX][startY] = 'X';
  //  printf("front = %d  back = %d\n", front, back);
  while (front < back && back < MAX_SIZE) {
    root = queue[front++];
    if (root.x == goalX && root.y == goalY) {
      free(queue);
      return root.movements;
    }

    int vx[] = {-1, 0, 1, 0};
    int vy[] = {0, 1, 0, -1};
    for (int c = 0; c < 4; c++) {
      struct steps child = root;
      while (validPosition(grid_count, child.x + vx[c], child.y + vy[c]) &&
             grid[child.x + vx[c]][child.y + vy[c]] == '.') {
        child.x += vx[c];
        child.y += vy[c];
        child.movements = root.movements + 1;
        grid[child.x][child.y] = 'X';
        queue[back++] = child;
      }
    }
  }
  free(queue);
  return -1;
}