Queen's Attack II Discussions | Algorithms | HackerRank

Sort by

recency

|

1003 Discussions

|

  • + 0 comments

    Here is problem solution in Python, Java, C++, C and Javascript - https://programmingoneonone.com/hackerrank-queens-attack-ii-problem-solution.html

  • + 0 comments

    **simple python solution **

    >

    def queensAttack(n, k, r_q, c_q, obstacles):

    attacks = 0
    directions = [(1, 0),(-1, 0),(0, 1),(0, -1),(1, 1),(-1, 1),(1, -1), (-1, -1) ]
    
    obstacles = set(map(tuple, obstacles))
    
    for dr, dc in directions:
        r, c = r_q, c_q
        while True:
            r += dr
            c += dc
            if not (1 <= r <= n and 1 <= c <= n): 
                break
            if (r, c) in obstacles:
                break
            attacks += 1
    
    return attacks
    
  • + 0 comments

    My Java solution with linear time and o(k) space complexity:

    static Map<Integer, Set<Integer>> obstacleMap = new HashMap<>();
    
    public static int queensAttack(int n, int k, int r_q, int c_q, List<List<Integer>> obstacles) {
        // Clear the map in case the method is called multiple times
        obstacleMap.clear();
        
        // Populate the map
        for (List<Integer> obstacle : obstacles) {
            int r = obstacle.get(0), c = obstacle.get(1);
            obstacleMap.computeIfAbsent(r, x -> new HashSet<>()).add(c);
        }
    
        // Count all directions
        int total = 0;
        total += countDirection(n, r_q, c_q, -1, 0);  // up
        total += countDirection(n, r_q, c_q, 1, 0);   // down
        total += countDirection(n, r_q, c_q, 0, -1);  // left
        total += countDirection(n, r_q, c_q, 0, 1);   // right
        total += countDirection(n, r_q, c_q, -1, -1); // up-left
        total += countDirection(n, r_q, c_q, -1, 1);  // up-right
        total += countDirection(n, r_q, c_q, 1, -1);  // down-left
        total += countDirection(n, r_q, c_q, 1, 1);   // down-right
    
        return total;
    }
    
    // Generic method to count squares in one direction
    public static int countDirection(int n, int r, int c, int dr, int dc) {
        int count = 0;
        r += dr;
        c += dc;
        
        while (r >= 1 && r <= n && c >= 1 && c <= n) {
            if (obstacleMap.containsKey(r) && obstacleMap.get(r).contains(c)) break;
            count++;
            r += dr;
            c += dc;
        }
        return count;
    }
    
  • + 0 comments

    int queensAttack(int n, int k, int r_q, int c_q, vector> obstacles) {

    int counter = 0; 
    
    //Tower walk
    int leftCount = c_q - 1;
    int rightCount = n - c_q;
    int upCount = n - r_q;
    int downCount = r_q - 1;
    
    for (const auto& obstacle : obstacles) {
    
        if (obstacle[0] == r_q && obstacle[1] == c_q) {
            return 0;
        }
        else if (obstacle[0] == r_q && obstacle[1] < c_q) {
            leftCount = min(leftCount, c_q - obstacle[1] - 1);
        }
        else if (obstacle[0] == r_q && obstacle[1] > c_q) {
            rightCount = min(rightCount, obstacle[1] - c_q - 1);
        }
        else if (obstacle[1] == c_q && obstacle[0] > r_q) {
            upCount = min(upCount, obstacle[0] - r_q - 1);
        }
        else if (obstacle[1] == c_q && obstacle[0] < r_q) {
            downCount = min(downCount, r_q - obstacle[0] - 1);
        }
    }
    
    counter += (leftCount + rightCount + upCount + downCount);
    
    //bishop walk
    int rowDiff = n - r_q;
    int colDiff = c_q - 1;
    int leftTopDiag = min(rowDiff, colDiff);
    
    rowDiff = r_q - 1;
    colDiff = c_q - 1;
    int leftBottomDiag = min(rowDiff, colDiff);
    
    rowDiff = n - r_q;
    colDiff = n - c_q;
    int rightTopDiag = min(rowDiff, colDiff);
    
    rowDiff = r_q - 1; 
    colDiff = n - c_q;
    int rightBottomDiag = min(rowDiff, colDiff);
    
    for (const auto& obstacle : obstacles) {
        if (abs(obstacle[0] - r_q) == abs(obstacle[1] - c_q)) {
            if (obstacle[0] > r_q && obstacle[1] < c_q) {
                leftTopDiag = min(abs(obstacle[0] - r_q) - 1, leftTopDiag) ;
            }
            else if (obstacle[0] < r_q && obstacle[1] < c_q) {
                leftBottomDiag = min(abs(obstacle[0] - r_q) - 1, leftBottomDiag);
            }
            else if (obstacle[0] > r_q && obstacle[1] > c_q) {
                rightTopDiag = min(rightTopDiag, abs(obstacle[0] - r_q) - 1);
            }
            else if (obstacle[0] < r_q && obstacle[1] > c_q) {
                rightBottomDiag = min(rightBottomDiag, abs(obstacle[0] - r_q) - 1);
            }
        }
    }
    
    counter += (leftTopDiag + leftBottomDiag + rightTopDiag + rightBottomDiag);
    return counter;
    

    }

  • + 0 comments

    Hint 1- Just check all obstacles that they are on one of four lines. Then you will have at maximun eight obstacles. Hint 2 - then just calculate distance to obstacle or edge of the board.

    public static boolean isPointOnLines(int xc, int yc, int xt, int yt) {
        if (yt == yc && xt != xc) {
            return true;
        }
        if (xt == xc && yt != yc) {
            return true;
        }
        if ((xt - xc) == (yt - yc)) {
            return true;
        }
        if ((xt - xc) == (yc - yt)) {
            return true;
        }
        return false;
    }