Formatted question description: https://leetcode.ca/all/1222.html

1222. Queens That Can Attack the King (Medium)

On an 8x8 chessboard, there can be multiple Black Queens and one White King.

Given an array of integer coordinates queens that represents the positions of the Black Queens, and a pair of coordinates king that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.

Example 1:

Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
Output: [[0,1],[1,0],[3,3]]
Explanation:  
The queen at [0,1] can attack the king cause they're in the same row. 
The queen at [1,0] can attack the king cause they're in the same column. 
The queen at [3,3] can attack the king cause they're in the same diagnal. 
The queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1]. 
The queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0]. 
The queen at [2,4] can't attack the king cause it's not in the same row/column/diagnal as the king.

Example 2:

Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
Output: [[2,2],[3,4],[4,4]]

Example 3:

Input: queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
Output: [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]

Constraints:

1 <= queens.length <= 63
queens[0].length == 2
0 <= queens[i][j] < 8
king.length == 2
0 <= king[0], king[1] < 8
At most one piece is allowed in a cell.

Related Topics:
Array

Solution 1.

class Solution {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        final int SIDE = 8;
        Set<String> queensSet = new HashSet<String>();
        for (int[] queen : queens)
            queensSet.add(Arrays.toString(queen));
        int[][] directions = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
        List<List<Integer>> queensAttackList = new ArrayList<List<Integer>>();
        for (int[] direction : directions) {
            int row = king[0] + direction[0], column = king[1] + direction[1];
            while (row >= 0 && row < SIDE && column >= 0 && column < SIDE) {
                int[] position = {row, column};
                if (queensSet.contains(Arrays.toString(position))) {
                    List<Integer> curQueen = new ArrayList<Integer>(Arrays.asList(row, column));
                    queensAttackList.add(curQueen);
                    break;
                } else {
                    row += direction[0];
                    column += direction[1];
                }
            }
        }
        return queensAttackList;
    }
}

############

class Solution {
    private static final int N = 8;
    private int[][] dirs
        = new int[][] { {0, -1}, {0, 1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        Set<Integer> s = get(queens);
        List<List<Integer>> ans = new ArrayList<>();
        for (int[] dir : dirs) {
            int x = king[0], y = king[1];
            int a = dir[0], b = dir[1];
            while (x + a >= 0 && x + a < N && y + b >= 0 && y + b < N) {
                x += a;
                y += b;
                if (s.contains(x * N + y)) {
                    ans.add(Arrays.asList(x, y));
                    break;
                }
            }
        }
        return ans;
    }

    private Set<Integer> get(int[][] queens) {
        Set<Integer> ans = new HashSet<>();
        for (int[] queen : queens) {
            ans.add(queen[0] * N + queen[1]);
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/queens-that-can-attack-the-king/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& Q, vector<int>& K) {
        vector<vector<int>> ans;
        int board[8][8] = {};
        for (auto &v : Q) board[v[0]][v[1]] = 1;
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                if (dx == 0 && dy == 0) continue;
                int x = K[0], y = K[1];
                while (x >= 0 && y >= 0 && x < 8 && y < 8) {
                    if (board[x][y]) {
                        ans.push_back({ x, y });
                        break;
                    }
                    x += dx;
                    y += dy;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def queensAttacktheKing(
        self, queens: List[List[int]], king: List[int]
    ) -> List[List[int]]:
        n = 8
        s = {(i, j) for i, j in queens}
        ans = []
        for a, b in [
            [-1, 0],
            [1, 0],
            [0, -1],
            [0, 1],
            [1, 1],
            [1, -1],
            [-1, 1],
            [-1, -1],
        ]:
            x, y = king
            while 0 <= x + a < n and 0 <= y + b < n:
                x, y = x + a, y + b
                if (x, y) in s:
                    ans.append([x, y])
                    break
        return ans

func queensAttacktheKing(queens [][]int, king []int) [][]int {
	s := make(map[int]bool)
	n := 8
	for _, queen := range queens {
		s[queen[0]*n+queen[1]] = true
	}
	dirs := [8][2]int{ {0, -1}, {0, 1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} }
	var ans [][]int
	for _, dir := range dirs {
		x, y := king[0], king[1]
		a, b := dir[0], dir[1]
		for x+a >= 0 && x+a < n && y+b >= 0 && y+b < n {
			x, y = x+a, y+b
			if s[x*n+y] {
				ans = append(ans, []int{x, y})
				break
			}
		}
	}
	return ans
}

1222 - Queens That Can Attack the King

1222. Queens That Can Attack the King (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1222. Queens That Can Attack the King (Medium)

Solution 1.

All Problems

All Solutions