home inspection之后的repair cost estimate找谁做？# Living
x*0
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
请问大家有什么更有效率的想法吗？
题目巨长输入格式是
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
请问大家有什么更有效率的想法吗？
