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

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