每日一题之可以攻击国王的皇后

Posted on In

问题

在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。

给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。

后（英文：Queen，Unicode字符♕U+2655，♛U+2656）是国际象棋棋局中实力最强的一种棋子。 后可横直斜走，且格数不限。 吃子与走法相同。 因为后的实力最强，故而在兵升变时，虽然可以选择变为其他棋子，但绝大多数会选择升变为后。

思路

  1. 逆向思维，考虑国王周围的八个方向是否有后。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
	public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
		int[][] directions = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 } };
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		// enumerate all directions
		dirs: for (int i = 0; i < directions.length; i++) {
			int[] tmp = new int[2];
			tmp[0] = king[0];
			tmp[1] = king[1];
			int[] dir = directions[i];
			// extend
			while (!isCross(tmp)) {
				tmp[0] += dir[0];
				tmp[1] += dir[1];
				// compare all queens
				for (int j = 0; j < queens.length; j++) {
					if (Arrays.equals(tmp, queens[j])) {
						List<Integer> posList = new ArrayList<Integer>();
						posList.add(queens[j][0]);
						posList.add(queens[j][1]);
						res.add(posList);
						continue dirs;
					}
				}
			}
		}
		return res;
	}

	boolean isCross(int[] pos) {
		return !(pos[0] > -1 && pos[0] < 8 && pos[1] > -1 && pos[1] < 8);
	}
}

其他注意

  1. 低级错误：int[]类型是引用传递，没注意到导致bug.

另一个想法

  1. 直接将所有坐标的差值计算出来，计算是否满足对角线或直线的规则。
  2. 这么做的话，需要考虑是否有遮挡，也就是一个方向只能用一次（平方和小的）。
  3. 最后将坐标差值加上国王坐标，还原王后坐标。