Discussion on Queen's Attack II Challenge

Sort by

recency

|

1000 Discussions

|

12 hours ago+ 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;

}

1 week ago+ 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;
}

2 weeks ago+ 0 comments

import java.io.; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.regex.*;

public class Solution {

// Complete the queensAttack function below. static int queensAttack(int n, int k, int r, int c, int[][] obstacles) { HashMap> cache = new HashMap<>(); for (int i = 0; i < obstacles.length; i++) { if (cache.containsKey(obstacles[i][0])) { cache.get(obstacles[i][0]).add(obstacles[i][1]); } else { cache.put(obstacles[i][0], new HashSet()); cache.get(obstacles[i][0]).add(obstacles[i][1]); } } int counter = 0; // right for (int i = c + 1; i <= n; i++) { if (cache.containsKey(r) && cache.get(r).contains(i)) { break; } counter++; }

// left
for (int i = c - 1; i >= 1; i--) {
  if (cache.containsKey(r) && cache.get(r).contains(i)) {
    break;
  }
  counter++;
}

// down
for (int i = r + 1; i <= n; i++) {
  if (cache.containsKey(i) && cache.get(i).contains(c)) {
    break;
  }
  counter++;
}

// up
for (int i = r - 1; i >= 1; i--) {
  if (cache.containsKey(i) && cache.get(i).contains(c)) {
    break;
  }
  counter++;
}

// up-left
for (int i = r - 1, j = c - 1; i >= 1 && j >= 1; i--, j--) {
  if (cache.containsKey(i) && cache.get(i).contains(j)) {
    break;
  }
  counter++;
}

// up-right
for (int i = r - 1, j = c + 1; i >= 1 && j <= n; i--, j++) {
  if (cache.containsKey(i) && cache.get(i).contains(j)) {
    break;
  }
  counter++;
}

// down-right
for (int i = r + 1, j = c + 1; i <= n && j <= n; i++, j++) {
  if (cache.containsKey(i) && cache.get(i).contains(j)) {
    break;
  }
  counter++;
}

// down-left
for (int i = r + 1, j = c - 1; i <= n && j >= 1; i++, j--) {
  if (cache.containsKey(i) && cache.get(i).contains(j)) {
    break;
  }
  counter++;
}

return counter;

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] nk = scanner.nextLine().split(" ");

int n = Integer.parseInt(nk[0]);

int k = Integer.parseInt(nk[1]);

String[] r_qC_q = scanner.nextLine().split(" ");

int r_q = Integer.parseInt(r_qC_q[0]);

int c_q = Integer.parseInt(r_qC_q[1]);

int[][] obstacles = new int[k][2];

for (int i = 0; i < k; i++) {
  String[] obstaclesRowItems = scanner.nextLine().split(" ");
  scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

  for (int j = 0; j < 2; j++) {
    int obstaclesItem = Integer.parseInt(obstaclesRowItems[j]);
    obstacles[i][j] = obstaclesItem;
  }
}

int result = queensAttack(n, k, r_q, c_q, obstacles);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();

bufferedWriter.close();

scanner.close();

} }

2 weeks ago+ 0 comments

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

/*
 * 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
 */

int queensAttack(int n, int k, int r_q, int c_q, vector<vector<int>> obstacles) {
    // Directions: {row offset, col offset}
    vector<pair<int, int>> directions = {
        {-1,  0}, {1,  0}, {0, -1}, {0,  1}, 
        {-1, -1}, {-1,  1}, {1, -1}, {1,  1}
    };

    // Store obstacles for O(1) lookup
    set<pair<int, int>> obs;
    for (auto& o : obstacles) {
        obs.insert({o[0], o[1]});
    }

    int attackableSquares = 0;

    // Check each direction
    for (auto& dir : directions) {
        int r = r_q + dir.first;
        int c = c_q + dir.second;
        
        while (r >= 1 && r <= n && c >= 1 && c <= n && obs.find({r, c}) == obs.end()) {
            attackableSquares++;
            r += dir.first;
            c += dir.second;
        }
    }

    return attackableSquares;
}
int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);

    vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

    int n = stoi(first_multiple_input[0]);

    int k = stoi(first_multiple_input[1]);

    string second_multiple_input_temp;
    getline(cin, second_multiple_input_temp);

    vector<string> second_multiple_input = split(rtrim(second_multiple_input_temp));

    int r_q = stoi(second_multiple_input[0]);

    int c_q = stoi(second_multiple_input[1]);

    vector<vector<int>> obstacles(k);

    for (int i = 0; i < k; i++) {
        obstacles[i].resize(2);

        string obstacles_row_temp_temp;
        getline(cin, obstacles_row_temp_temp);

        vector<string> obstacles_row_temp = split(rtrim(obstacles_row_temp_temp));

        for (int j = 0; j < 2; j++) {
            int obstacles_row_item = stoi(obstacles_row_temp[j]);

            obstacles[i][j] = obstacles_row_item;
        }
    }

    int result = queensAttack(n, k, r_q, c_q, obstacles);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}

2 weeks ago+ 1 comment

Python 3 My code runs by doing a few things for each calculation: 1. determine all the obstacles that are in line with my queen (above and below, left and right, top left to bottom right diagonal, and top right to bottom left diagonal) 2. to count an attackable square it needs to be: in bounds and before the first object in line with the queen in the given direction 3. for the 4 cardinal directions (up, down, left, right) I only need to check the appriate row or column, for the 4 ordinal directions (the diagonals) I must check for the appropriate row and column 4. I finally add the available attacks from all 8 directions and return it

def queensAttack(n, k, r_q, c_q, obstacles):
    # Write your code here
    attacks = 0
    #up
    same_col = [obs for obs in obstacles if obs[1] == c_q]
    above_r = r_q + 1
    up_attacks = 0
    while above_r <= n and all(above_r < obs[0] for obs in same_col if obs[0] > r_q):
        up_attacks += 1
        above_r += 1
    #print(f'above: {up_attacks}')#debugging
    
    #down
    below_r = r_q - 1
    down_attacks = 0
    while below_r > 0 and all(below_r > obs[0] for obs in same_col if obs[0] < r_q):
        down_attacks += 1
        below_r -= 1
    #print(f'below: {down_attacks}')#debugging
    
    #left
    same_row = [obs for obs in obstacles if obs[0] == r_q]
    left_c = c_q - 1
    left_attacks = 0
    while left_c > 0 and all(left_c > obs[1] for obs in same_row if obs[1] < c_q):
        left_attacks += 1
        left_c -= 1
    #print(f'left: {left_attacks}')#debugging
    
    #right
    right_c = c_q + 1
    right_attacks = 0
    while right_c <= n and all(right_c < obs[1] for obs in same_row if obs[1] > c_q):
        right_attacks += 1
        right_c += 1
    #print(f'right: {right_attacks}')#debugging
    
    #diag up left
    left_right_diag = [obs for obs in obstacles if obs[0] - r_q == c_q - obs[1]]
    up_left_row = r_q + 1
    up_left_col = c_q - 1
    up_left_attacks = 0
    while up_left_row <= n and up_left_col > 0 and all(up_left_row < obs[0] and up_left_col > obs[1] for obs in left_right_diag if obs[0] > r_q and obs[1] < c_q):
        up_left_attacks += 1
        up_left_row += 1
        up_left_col -= 1
    #print(f'up left: {up_left_attacks}')#debugging
    
    #diag down right
    down_right_row = r_q - 1
    down_right_col = c_q + 1
    down_right_attacks = 0
    while down_right_row > 0 and down_right_col <= n and all(down_right_row > obs[0] and down_right_col < obs[1] for obs in left_right_diag if obs[0] < r_q and obs[1] > c_q):
        down_right_attacks += 1
        down_right_row -= 1
        down_right_col += 1
    #print(f'down right: {down_right_attacks}') #debugging
    
    #diag up right
    right_left_diag = [obs for obs in obstacles if obs[0] - r_q == obs[1] - c_q]
    up_right_row = r_q + 1
    up_right_col = c_q + 1
    up_right_attacks = 0
    while up_right_row <= n and up_right_col <= n and all(up_right_row < obs[0] and up_right_col < obs[1] for obs in right_left_diag if obs[0] > r_q and obs[1] > c_q):
        up_right_attacks += 1
        up_right_row += 1
        up_right_col += 1
    #print(f'up right: {up_right_attacks}') #debugging
    
    #diag down left
    down_left_row = r_q - 1
    down_left_col = c_q - 1
    down_left_attacks = 0
    while down_left_row > 0 and down_left_col > 0 and all(down_left_row > obs[0] and down_left_col > obs[1] for obs in right_left_diag if obs[0] < r_q and obs[1] < c_q):
        down_left_attacks += 1
        down_left_row -= 1
        down_left_col -= 1
    #print(f'down left: {down_left_attacks}') #debugging

    attacks = up_attacks + down_attacks + left_attacks + right_attacks + up_left_attacks + down_right_attacks + up_right_attacks + down_left_attacks
    #print(attacks) #debugging
    return attacks

2 days ago+ 0 comments

dawg

Sort by

|

1000 Discussions

|

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge