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。(由于输入限制)所以只要考虑对角线 和逆对 : 角线。
|
|