Queen's Attack II Discussions | Algorithms | HackerRank

Sort by

recency

|

1012 Discussions

|

  • + 0 comments

    import java.util.*; import java.awt.Point;

    //thank me later public class Solution { public static void main(String[] args){ Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int k = in.nextInt();
    
        Point queen = new Point(in.nextInt(), in.nextInt());
    
        HashSet<Point> obstacles = new HashSet<Point>();
    
        for(int i = 0; i < k; i++){
            obstacles.add(new Point(in.nextInt(), in.nextInt()));
        }
    
        Stack<Direction> directions = getAllDirections();
        int possiblePoints = 0;
    
        while(!directions.empty()){
            Direction d = directions.pop();
            Point cur = new Point(queen);
            cur.translate(d.x, d.y);
    
            while(isInside(cur, n) && !obstacles.contains(cur)){
                possiblePoints++;
                cur.translate(d.x, d.y);
            }
        }
    
        System.out.println(possiblePoints);
    }
    
    private static boolean isInside(Point p, int n){
        return p.x > 0 && p.y > 0 && p.x <= n && p.y <= n;
    }
    
    private static Stack<Direction> getAllDirections(){
        Stack<Direction> directions = new Stack<Direction>();
        directions.push(new Direction(0, 1));
        directions.push(new Direction(1, 1));
        directions.push(new Direction(1, 0));
        directions.push(new Direction(1, -1));
        directions.push(new Direction(0, -1));
        directions.push(new Direction(-1, -1));
        directions.push(new Direction(-1, 0));
        directions.push(new Direction(-1, 1));
        return directions;
    }
    
    private static class Direction {
        int x, y;
        public Direction(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    

    }

  • + 0 comments

    Cries in no. 1 grid problem hater:

    int queensAttack(int n, int k, int r_q, int c_q, vector<vector<int>> obstacles) {
        set<pair<int,int>> obs;
        for (auto &o : obstacles) {
            obs.insert({o[0], o[1]});
        }
    
        vector<pair<int,int>> directions = {
            {1, 0}, {-1, 0}, {0, 1}, {0, -1},
            {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
        };
    
        int count = 0;
    
        for (auto [dr, dc] : directions) {
            int r = r_q + dr;
            int c = c_q + dc;
    
            while (r >= 1 && r <= n && c >= 1 && c <= n && !obs.count({r,c})) {
                count++;
                r += dr;
                c += dc;
            }
        }
    
        return count;
    }
    
  • + 0 comments

    step 1: calculate the maximum attacks in eight directions; step 2: if there is obstacle in any one of the eight direction, which one smaller is the distance. def queensAttack(n, k, r_q, c_q, obstacles): # Write your code here dir_dis = {(0,1):n-c_q, (0,-1):c_q - 1, (1, 0): n-r_q, (-1, 0): r_q - 1, (-1, -1):min(r_q - 1, c_q - 1), (1, 1):min(n-r_q, n-c_q), (1, -1): min(n-r_q, c_q-1), (-1, 1):min(r_q-1, n-c_q) } for ro, co in obstacles: dx = ro - r_q dy = co - c_q if dx == 0 or dy == 0 or abs(dx) == abs(dy): dis = abs(dx) if abs(dx) == abs(dy) else max(abs(dx), abs(dy)) di = (dx/dis, dy/dis) dir_dis[di] = min(dir_dis[di], dis - 1) return sum(dir_dis.values())

  • + 0 comments

    This code works..!! Huhh.. finallyy..!!:)) def queensAttack(n, k, r_q, c_q, obstacles): obstacle_set = {(r, c) for r, c in obstacles} moves = 0 directions = [ (1, 0), # Up (-1, 0), # Down (0, 1), # Right (0, -1), # Left (1, 1), # Up-right (1, -1), # Up-left (-1, 1), # Down-right (-1, -1) # Down-left ] for dr, dc in directions: r, c = r_q + dr, c_q + dc while 1 <= r <= n and 1 <= c <= n: if (r, c) in obstacle_set: break moves += 1 r += dr c += dc return moves if name == 'main': n, k = map(int, input().split()) r_q, c_q = map(int, input().split()) obstacles = [tuple(map(int, input().split())) for _ in range(k)] print(queensAttack(n, k, r_q, c_q, obstacles))

    `

  • + 1 comment

    Here's my inefficient code :D I suck at grid problems

    def is_available_move(initial_position, i, j, obstacles, n):
        if (i > 0 and i <= n) and (j > 0 and j <= n):
            if [i,j] not in obstacles and (i, j) != initial_position:
                return True
        return False
    
    def queensAttack(n, k, r_q, c_q, obstacles):
        initial_position = (r_q, c_q) # queen's initial position
        
        # 8 directions from queen's initial position
        top_left_d = []
        top_v = []
        top_right_d = []
        right_h = []
        bottom_right_d = []
        bottom_v = []
        bottom_left_d = []
        left_h = []
        
        # find all moves from initial position to top left diagonal
        print("now calculating top_left_diagonal")
        j = c_q
        for i in range(r_q, n):
            i += 1
            j -= 1
            print("what's i",i, "what's j", j)
            if is_available_move(initial_position, i, j, obstacles, n):
                top_left_d.append((i,j))
            else:
                break
        print(top_left_d)
    
        # find all moves from initial position to top vertical 
        print("now calculating top_v")
        for i in range(r_q, n):
            i += 1 
            j = c_q
            if is_available_move(initial_position, i, j, obstacles, n):
                top_v.append((i, j))
            else:
                break
        print(top_v)
                
        # find all moves from initial position to top right diagonal 
        print("now calculating top_right_diagonal")
        j = c_q
        for i in range(r_q, n):
            i += 1  
            j += 1
            if is_available_move(initial_position, i, j, obstacles, n):
                top_right_d.append((i,j))
            else:
                break
        print(top_right_d)
                    
        # find all moves from initial position to right horizontal row
        print("now calculating right_h")
        for j in range(c_q, n):
            j += 1 
            i = r_q
            if is_available_move(initial_position, i, j, obstacles, n):
                right_h.append((i,j))
            else:
                break
        print(right_h) 
        
        # find all moves from initial position to bottom right diagonal
        print("now calculating bottom_right_diagonal")
        j = c_q
        for i in range(r_q , 0, -1):
            i -= 1
            j += 1
            if is_available_move(initial_position, i, j, obstacles, n):
                bottom_right_d.append((i,j))
            else:
                break
        print(bottom_left_d)
                    
                    
        # find all moves from initial position to bottom vertical 
        print("now calculating bottom_v")
        for i in range(r_q, 0, -1):
            i -= 1
            j = c_q
            if is_available_move(initial_position, i, j, obstacles, n):
                bottom_v.append((i, j))
            else:
                break
        print(bottom_v)
        
        # find all moves from initial position to bottom left diagonal
        print("now calculating bottom_left_diagonal")
        j = c_q
        for i in range(r_q, 0, -1):
            i -= 1
            j -= 1
            if is_available_move(initial_position, i, j, obstacles, n):
                bottom_left_d.append((i,j))
            else:
                break
        print(bottom_left_d)
                
        # find all moves from initial position to left horizontal row
        print("now calculating left_h")
        for j in range(c_q, 0, -1):
            j -= 1
            i = r_q
            if is_available_move(initial_position, i, j, obstacles, n):
                left_h.append((i,j))        
            else:
                break
        print(left_h)
    
        # print("what's our moves: ", top_left_d + top_v + top_right_d + right_h + bottom_right_d + bottom_v + bottom_left_d + left_h)
        return len(top_left_d + top_v + top_right_d + right_h + bottom_right_d + bottom_v + bottom_left_d + left_h)