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

|

37 Discussions

|

  • hacker_n6e15uxz
     + 0 comments

    There are 2 issues * player can stop anywhere and change direction, does not need to go "until it reaches the edge of the grid or a blocked cell" * Xs and Ys are swapped, iterating over Xs == going through the rows

    C++ solution:

    using xy_distance = array<int, 3>;
char visited[100][100];

int minimumMoves(vector<string> grid, int startX, int startY, int goalX, int goalY) {
    // iterating over Xs == iterating over rows in the problem statement
    int start_row = startX;
    int start_col = startY;
    int goal_row = goalX;
    int goal_col = goalY;
    
    int rows = grid.size();
    int cols = grid[0].size();
    
    memset(visited, 0, sizeof visited);
    queue<xy_distance> q;
    
    auto visit = [&](int r, int c, int d) {
        if (!visited[r][c]) {
            q.push({r, c, d});
            visited[r][c] = 1;
        }
    };
    
    auto move = [&](int row, int col, int d, int row_dir, int col_dir) {
        int r=row, c=col;
        
        while (r >= 0 && c >= 0 && r < rows && c < cols) {
            if (grid[r][c] == 'X') {
                break;
            } else {
                visit(r, c, d+1);
            }
            
            r += row_dir;
            c += col_dir;
        }
    };
    
    visit(start_row, start_col, 0);
    
    while (!q.empty()) {
        auto [r, c, d] = q.front(); q.pop();
        
        if (r == goal_row && c == goal_col) {
            return d;
        }
        
        move(r, c, d, -1,  0);
        move(r, c, d, +1,  0);
        move(r, c, d,  0, -1);
        move(r, c, d,  0, +1);
    }
    
    return -1;
}

  • s_hmnd
     + 0 comments
    #First, build the neighborhood of nodes: for a given position, move in all directions and add possible nodes to the adjacency list
# Then, do a BFS from start node, until we reach end node, count how many levels of BFS traversal needed 

from collections import defaultdict, deque
def check_go(i, j, d_i, d_j, grid, ngbs_ij):
    n = len(grid)
    cur_i = i + d_i
    cur_j = j + d_j
    while 0 <= cur_i < n and 0 <= cur_j < n and grid[cur_i][cur_j]=='.':
        ngbs_ij.append((cur_i, cur_j))
        cur_i += d_i
        cur_j += d_j
        
def build_ngbs(grid):
    ngbs = defaultdict(list)
    n = len(grid)
    for i in range(n):
        for j in range(n):
            if grid[i][j] == '.':
                #check ngbs
                check_go(i, j, 0, -1, grid, ngbs[(i,j)])
                check_go(i, j, 0, +1, grid, ngbs[(i,j)])
                check_go(i, j, -1, 0, grid, ngbs[(i,j)])
                check_go(i, j, +1, 0, grid, ngbs[(i,j)])
    return ngbs  
                

def minimumMoves(grid, startX, startY, goalX, goalY):
    ngbs = build_ngbs(grid)
    q = deque()
    visited = set()
    q.append((startX, startY))
    visited.add((startX, startY))
    level_counter = -1
    while q:
        level_size = len(q)
        level_counter+=1
        for _ in range(level_size):
            node = q.popleft()
            if node==(goalX, goalY):
                return level_counter
            for neighbor in ngbs[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)

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