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

|

332 Discussions

|

  • 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

  • manceraaxel
     + 0 comments

    from collections import deque

    def minimumMoves(grid, startX, startY, goalX, goalY): n = len(grid) directions = ( (-1, 0), (0, 1), (1, 0), (0, -1), ) queue = deque( [(startX, startY, 0)] ) visited = set( [(startX, startY)] )

    # BFS
while queue:
    current_x, current_y, current_distance = queue.popleft()

    if (current_x, current_y) == (goalX, goalY):
        return current_distance

    # Visit current node neighbors
    for move_to_x, move_to_y in directions:
        next_x, next_y = current_x, current_y

        # Move until reaching grid's edge or facing an obstacle "X"
        while (
            0 <= next_x + move_to_x < n
            and 0 <= next_y + move_to_y < n
            and grid[next_x + move_to_x][next_y + move_to_y]
            != "X"
        ):
            next_x += move_to_x
            next_y += move_to_y


            if (next_x, next_y) == (goalX, goalY):
                return current_distance + 1

        if (next_x, next_y) not in visited:
            visited.add((next_x, next_y))
            queue.append((next_x, next_y, current_distance + 1))

return -1

  • dehaka
     + 0 comments

    simply O(n^3) algo

    void update(int I, int J, int i, int j, vector<vector<bool>>& visited, vector<vector<int>>& minPath, queue<pair<int, int>>& Q) {
    if (visited[i][j]) return;
    visited[i][j] = true;
    minPath[i][j] = minPath[I][J] + 1;
    Q.push(make_pair(i, j));
    return;
}

int minimumMoves(int n, vector<vector<char>> grid, int startX, int startY, int goalX, int goalY) {
    vector<vector<bool>> visited(n + 2, vector<bool>(n + 2));
    vector<vector<int>> minPath(n + 2, vector<int>(n + 2, -1));
    queue<pair<int, int>> Q;
    Q.push(make_pair(startX, startY));
    visited[startX][startY] = true;
    minPath[startX][startY] = 0;
    while (!Q.empty()) {
        int I = Q.front().first, J = Q.front().second;
        for (int i=1; I - i > 0; i++) {
            if (grid[I-i][J] == 'X') break;
            update(I, J, I-i, J, visited, minPath, Q);
        }
        for (int i=1; I + i < n+1; i++) {
            if (grid[I+i][J] == 'X') break;
            update(I, J, I+i, J, visited, minPath, Q);
        }
        for (int j=1; J - j > 0; j++) {
            if (grid[I][J-j] == 'X') break;
            update(I, J, I, J-j, visited, minPath, Q);
        }
        for (int j=1; J + j < n+1; j++) {
            if (grid[I][J+j] == 'X') break;
            update(I, J, I, J+j, visited, minPath, Q);
        }
        Q.pop();
    }
    return minPath[goalX][goalY];
}

int main()
{
    int n, startX, startY, goalX, goalY;
    string s;
    cin >> n;
    vector<vector<char>> grid(n + 2, vector<char>(n + 2));
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= n; j++) grid[i][j] = s[j - 1];
    }
    cin >> startX >> startY >> goalX >> goalY;
    cout << minimumMoves(n, grid, startX + 1, startY + 1, goalX + 1, goalY + 1);
}

  • gurmeharsinghv
     + 0 comments

    Python easy implementation using deque:

    import os from collections import deque

    def minimumMoves(grid, startX, startY, goalX, goalY): # Define the directions for up, down, left, right movements directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # Create a queue for BFS and enqueue the starting position with 0 moves
queue = deque([(startX, startY, 0)])

# Create a set to keep track of visited positions
visited = set()
visited.add((startX, startY))

# Get the size of the grid
n = len(grid)

# Perform BFS
while queue:
    x, y, moves = queue.popleft()

    # Check if we have reached the goal
    if (x, y) == (goalX, goalY):
        return moves

    # Try all 4 possible directions
    for dx, dy in directions:
        nx, ny = x, y

        # Move in the current direction until hitting a wall or boundary
        while 0 <= nx + dx < n and 0 <= ny + dy < n and grid[nx + dx][ny + dy] == '.':
            nx += dx
            ny += dy

            # If this new position has not been visited, add it to the queue
            if (nx, ny) not in visited:
                queue.append((nx, ny, moves + 1))
                visited.add((nx, ny))

# If the goal is not reachable, return -1 (though in the problem it's guaranteed to be reachable)
return -1

    if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

grid = []

for _ in range(n):
    grid_item = input()
    grid.append(grid_item)

first_multiple_input = input().rstrip().split()

startX = int(first_multiple_input[0])

startY = int(first_multiple_input[1])

goalX = int(first_multiple_input[2])

goalY = int(first_multiple_input[3])

result = minimumMoves(grid, startX, startY, goalX, goalY)

    deque helps in improving time complexity to O(1) ... while append and pop the points/elements.

    fptr.write(str(result) + '\n')

fptr.close()