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. Castle on the Grid
  2. Discussions

Castle on the Grid

Sort by

recency

|

35 Discussions

|

  • engnr_plusplus
     + 1 comment

    This problm's got issues. Let's take the first test case:

    [s X .] [. X .] [g . .]

    to go from Start to Goal, there are two moves (0,0)->(0,1) and (0,1)->(0,2). But the expected answer is 3. How TF are they counting to get to 3? Can somebody please explain to me? Or, at least, share whatever the author was smoking?

  • maglione_k
     + 0 comments

    If you're getting results that seem correct but don't match the expected results (e.g., 1 rather than 3 for sample test 0), it's probably because x and y are not fully specified in the problem description, and you have them reversed. The first row of input is the column x=0 rather than the row y=0. You can swap the X and Y argument names in the minimumMoves function to resolve it.

  • amr_m_ezzat
     + 0 comments

    solution in C#: 

        private static readonly List<(int dx, int dy)> directions = new()
    {
        (1, 0), (-1, 0), (0, 1), (0, -1)
    };

    public static int minimumMoves(List<string> grid, int startX, int startY, int goalX, int goalY)
    {
        var len = grid.Count;
        var queue = new Queue<(int cx, int cy, int moves)>();
        var visited = new bool[len, len];
        
        queue.Enqueue((startX, startY, 0));
        visited[startX, startY] = true;
        
        while(queue.Count > 0)
        {
            var (cx, cy, moves) = queue.Dequeue();
            
            if(cx == goalX && cy == goalY)
            {
                return moves;
            }
            
            foreach(var (dx, dy) in directions)
            {
                var (nx, ny) = (cx + dx, cy + dy);
                while (nx >= 0 && nx < len && 
                    ny >= 0 && ny < len && 
                    grid[nx][ny] == '.')
                {
                    if (!visited[nx, ny])
                    {
                        visited[nx, ny] = true;
                        queue.Enqueue((nx, ny, moves + 1));
                    }

                    nx += dx;
                    ny += dy;
                }
            }
        }
        
        return -1;
    }

  • 1337er
     + 0 comments

    i solved by building a graph of points on the grid and calculating distance using dijkstra's algo

    from collections import defaultdict
import heapq


def dijkstra(graph, start):
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    previous_nodes = {node: None for node in graph}
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances, previous_nodes
 

def minimumMoves(grid, startX, startY, goalX, goalY):
    # Write your code here
    nodes = defaultdict(dict)
    length = len(grid[0])
    # create graph of nodes and edges
    for y, row in enumerate(grid):
        for x, column in enumerate(row):
            if grid[y][x] == "X":
                continue
            # move up and add edges
            i, j = x-1, y
            # go left
            while i >= 0 and grid[j][i] != "X":
                nodes[(x, y)][(i, j)] = 1
                i -= 1
            # go right
            i, j = x+1, y
            while i < length and grid[j][i] != "X":
                nodes[(x, y)][(i, j)] = 1
                i += 1
            i, j = x, y-1
            # go down
            while j >= 0 and grid[j][i] != "X":
                nodes[(x, y)][(i, j)] = 1
                j -= 1
            # go up
            i, j = x, y+1
            while j < length and grid[j][i] != "X":
                nodes[(x, y)][(i, j)] = 1
                j += 1
    maps = dijkstra(nodes, (startY, startX))
    return maps[0][(goalY, goalX)]

  • tunghan0916
     + 0 comments

    If you are using BFS, simply blocking the previously visited spots might not work, you can try to add it if its cost is less.