1222. Queens That Can Attack the King

yPhantom 2019年10月14日 64次浏览

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.

Solution

以国王为中心,向8个方向进行遍历,找到王后就记录并返回。

class Solution {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        List<List<Integer>> resultList = new ArrayList<>();
        boolean[][] visited = new boolean[8][8];
        
        for (int[] queen: queens) {
            visited[queen[0]][queen[1]] = true;
        }
        
        // dr -> direction row
        for(int dr = -1; dr <= 1; dr++) {
            // dc -> direction column
            for (int dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) {
                    continue;
                }
                List<Integer> attackQueen = doSearch(visited, king, dr, dc);
                if (attackQueen != null) {
                    resultList.add(attackQueen);
                }
            }
        }
        return resultList;
    }
    
    public List<Integer> doSearch(boolean[][] visited, int[] king, int dr, int dc) {
        int r = king[0] + dr;
        int c = king[1] + dc;
        while (r >= 0 && c >= 0 && r < 8 && c < 8) {
            if (visited[r][c]) {
                return Arrays.asList(r, c);
            }
            // 继续查找
            r += dr;
            c += dc;
        }
        return null;
    }
}