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

|

335 Discussions

|

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

  • illogicalsleepi1
     + 0 comments
    from collections import deque

def minimumMoves(grid, startX, startY, goalX, goalY):
    n = len(grid)
    m = len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]    
    queue = deque([(startX, startY, 0)])  
    visited = set()
    visited.add((startX, startY))
    while queue:
        x, y, moves = queue.popleft()        
        if (x, y) == (goalX, goalY):
            return moves        
        for dx, dy in directions:
            nx, ny = x, y
            while 0 <= nx + dx < n and 0 <= ny + dy < m and grid[nx + dx][ny + dy] != 'X':
                nx += dx
                ny += dy
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny, moves + 1))    
    return -1