x*****0
发帖数: 452 | 1 N queen 变种
题目巨长输入格式是
1
2
就是说 第1行第1个是queen 第2行第2个是queen，并保证输入的数字不重复，这样可以
得出一个结论：同一行 同一列不会出现2个queen。
题目要求是求出 对于每个Queen， 最大的威胁次数，威胁指只要一个queen所能移动的
范围内有别的queen就算威胁 P.S.同一方向上有2个queen威胁你 只算最近的那个。
由于同一行 同一列不会出现2个queen。（由于输入限制）所以只要考虑对角线 和逆对
角线。
举个例子： 棋盘是：
100 ---- 1号 queen. From 1point 3acres bbs
010 ---- 2号 queen
001 ---- 3号 queen
1号和3号queen的受威胁次数都是1， 2号是2（被1和3） 所以答案是2
只想到了一个brute force search的解法。
伪代码：
threats = [0]*len(queens)
for i = [0: len(queens)-1]
four_directions = [false]*4 #四个对角线方向:0,1,2,3
for j = [i+1 : len(queens)-1]
flag = is_thread(queens[i], queens[j]) #flag belongs to [-1,0,1,2,3]
if (flag > 0 and four_directions[flag] == false)
threats[i] = threats[i] + 1
请问大家有什么更有效率的想法吗？ |
x*****0
发帖数: 452 | |
s********a
发帖数: 1447 | 3 不会下棋 queen的活动范围多大啊？
只可以跳到相邻的对角线 还是可以跳好远？ |
l******s
发帖数: 3045 | 4 不限格数
【在 s********a 的大作中提到】
: 不会下棋 queen的活动范围多大啊？
: 只可以跳到相邻的对角线 还是可以跳好远？
|
j**********3
发帖数: 3211 | |
f***k
发帖数: 147 | 6 方向上来看，横竖都不用算，Queen 数大于1的时候，横竖的最大威胁肯定是1。
所以只考虑对角线方向移动所受威胁。 |
J*******o
发帖数: 741 | 7
最近不是很火吗
【在 j**********3 的大作中提到】
: 这公司还有人敢去面？这么多负面消息
|
x*****n
发帖数: 195 | 8 还有就是把所有对角线都扫描一遍，也就是所有格子都会扫描两边，复杂度也是N*N。
但是判断threat关系的code好写一些。
【在 x*****0 的大作中提到】
: N queen 变种
: 题目巨长输入格式是
: 1
: 2
: 就是说 第1行第1个是queen 第2行第2个是queen，并保证输入的数字不重复，这样可以
: 得出一个结论：同一行 同一列不会出现2个queen。
: 题目要求是求出 对于每个Queen， 最大的威胁次数，威胁指只要一个queen所能移动的
: 范围内有别的queen就算威胁 P.S.同一方向上有2个queen威胁你 只算最近的那个。
: 由于同一行 同一列不会出现2个queen。（由于输入限制）所以只要考虑对角线 和逆对
: 角线。
|
