Queen's Attack II Discussions | Algorithms | HackerRank

Sort by

recency

|

1005 Discussions

|

  • + 0 comments

    Given plenty of time, I can complete medium diffcult level problem. but I cannot complate in half an hour.

  • + 0 comments
    /*
     * Complete the 'queensAttack' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER k
     *  3. INTEGER r_q
     *  4. INTEGER c_q
     *  5. 2D_INTEGER_ARRAY obstacles
     */
    
    void _info(int n, int k, int r_q, int c_q, vector<vector<int>> obstacles) {
        cout << "n: " << n << endl;
        cout << "q: " << r_q << "," << c_q << endl;
        for (auto ob: obstacles) {
            auto r = ob[0];
            auto c = ob[1];
            cout << "o: " << r << ',' << c << endl;
        }    
    }
    
    int _north(int n, int r_q, int c_q, const vector<vector<int>>& obstacles) {
        vector<int> z = { r_q };
        for (auto ob: obstacles) {
            if (ob[1] == c_q) {
                auto dr = r_q - ob[0];
                if (dr > 0) { z.push_back(dr); }
            }
        }
        auto d = *min_element(z.begin(), z.end());
        return d - 1;
    }
    
    int _east(int n, int r_q, int c_q, const vector<vector<int>>& obstacles) {
        vector<int> z = { n + 1 - c_q };
        for (auto ob: obstacles) {
            if (ob[0] == r_q) {
                auto dc = ob[1] - c_q;
                if (dc > 0) { z.push_back(dc); }
            }
        }
        auto d = *min_element(z.begin(), z.end());
        return d - 1;
    }
    
    int _south(int n, int r_q, int c_q, const vector<vector<int>>& obstacles) {
        vector<int> z = { n + 1 - r_q };
        for (auto ob: obstacles) {
            if (ob[1] == c_q) {
                auto dr = ob[0] - r_q;
                if (dr > 0) { z.push_back(dr); }
            }
        }
        auto d = *min_element(z.begin(), z.end());
        return d - 1;
    }
    
    int _west(int n, int r_q, int c_q, const vector<vector<int>>& obstacles) {
        vector<int> z = { c_q };
        for (auto ob: obstacles) {
            if (ob[0] == r_q) {
                auto dc = c_q - ob[1];
                if (dc > 0) { z.push_back(dc); }
            }
        }
        auto d = *min_element(z.begin(), z.end());
        return d - 1;
    }
    
    int _ne(int n, int r_q, int c_q, const vector<vector<int>>& obstacles) {
        int k = min(r_q, n + 1 - c_q);
        vector<int> z = {k};
        for (auto ob: obstacles) {
            auto dr = r_q - ob[0];
            auto dc = ob[1] - c_q;
            if ((dr > 0) && (dr == dc)) { z.push_back(dr); }
        }
        auto d = *min_element(z.begin(), z.end());
        return d - 1;
    }
    
    int _se(int n, int r_q, int c_q, const vector<vector<int>>& obstacles) {
        int k = min(n + 1 - r_q, n + 1 - c_q);
        vector<int> z = {k};
        for (auto ob: obstacles) {
            auto dr = ob[0] - r_q;
            auto dc = ob[1] - c_q;
            if ((dr > 0) && (dr == dc)) { z.push_back(dr); }
        }
        auto d = *min_element(z.begin(), z.end());
        return d - 1;
    }
    
    int _sw(int n, int r_q, int c_q, const vector<vector<int>>& obstacles) {
        int k = min(n + 1 - r_q, c_q);
        vector<int> z = {k};
        for (auto ob: obstacles) {
            auto dr = ob[0] - r_q;
            auto dc = c_q - ob[1];
            if ((dr > 0) && (dr == dc)) { z.push_back(dr); }
        }
        auto d = *min_element(z.begin(), z.end());
        return d - 1;
    }
    
    int _nw(int n, int r_q, int c_q, const vector<vector<int>>& obstacles) {
        int k = min(r_q, c_q);
        vector<int> z = {k};
        for (auto ob: obstacles) {
            auto dr = r_q - ob[0];
            auto dc = c_q - ob[1];
            if ((dr > 0) && (dr == dc)) { z.push_back(dr); }
        }
        auto d = *min_element(z.begin(), z.end());
        return d - 1;
    }
    
    int queensAttack(int n, int k, int r_q, int c_q, vector<vector<int>> obstacles) {
        
        // _info(n, k, r_q, c_q, obstacles);
        
        int cnt = 0;
        cnt += _north(n, r_q, c_q, obstacles);
        cnt += _east(n, r_q, c_q, obstacles);
        cnt += _south(n, r_q, c_q, obstacles);
        cnt += _west(n, r_q, c_q, obstacles);
        cnt += _ne(n, r_q, c_q, obstacles);
        cnt += _se(n, r_q, c_q, obstacles);
        cnt += _sw(n, r_q, c_q, obstacles);
        cnt += _nw(n, r_q, c_q, obstacles);
        
        // cout << cnt << endl;
        return cnt;
    }
    
  • + 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;
    }