如何从特定点获取对角线值？
How to get diagonal values from specific point?
假设我有一个包含以下数据的 10x10 矩阵：
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 38 39 40
41 42 43 44 _ 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
我的位置在[4][4]。如何列出此位置的对角线值？
例如，预期结果为：
[56, 67, 78, 89, 100, 1, 12, 23, 34]
[54, 63, 72, 81, 9, 18, 27, 36]
我目前的解决方案
def next?(index, row, size)
(((row + index) % size) + 1 ) % size
end
(1...chess_size).each do |l|
next_el, curr_el = next?(l, row, chess_size), (row + l) % chess_size
# this gets me the first diagnonal. Note that it prints out wrong value
tmp[0] << chess[curr_el][curr_el]
# this gets me the values from current row below to up
tmp[1] << chess[(row + l) % chess_size][row]
tmp[2] << chess[-l][l]
tmp[3] << chess[row][(row + l) % chess_size]
end
我们的矩阵将始终具有相同的行数和列数。
通常要从 i 和 j 获取对角线值，您可以同时迭代 i 和 j，最多其中一个是零。因此，主对角线是 (i-1, j-1), (i-2, j-2), ... 到 i, j >= 0 和 (i + 1, j + 1), (i +2, j + 2), ... 到 i, j <= n。因为反对角线是 (i - 1, j + 1), (i - 2, j + 2), ... 到 i >= 0 和 j <= n，并且 (i + 1, j-1), (i + 2, j - 2), ... 到 i <= n 和 j >= 0.
我刚刚从 OP 发表的评论中得知我解决了错误的问题，尽管事实上 OP 的问题看起来很清楚，尤其是示例，并且与我的解释一致。我将把这个解决方案留给以下问题：“给定一个数组 arr，使得 Matrix(*arr) 是一个 NxM 矩阵，矩阵位置 i,j，return 一个数组 [d,a]，其中元素 d 和 a 是通过 [d,a] 但不包括 [d,a] 的对角线和反对角线上的元素，并且每个元素都旋转，以便行索引如果 i < arr.size-1，第一个元素是 i+1，否则是 0。
代码
def diagonals(arr, row_idx, col_idx)
ncols = arr.first.size
sum_idx = row_idx+col_idx
diff_idx = row_idx-col_idx
a = Array.new(arr.size * arr.first.size) { |i| i.divmod(ncols) } -[[row_idx, col_idx]]
[a.select { |r,c| r-c == diff_idx }, a.select { |r,c| r+c == sum_idx }].
map do |b| b.sort_by { |r,_| [r > row_idx ? 0:1 , r] }.
map { |r,c| arr[r][c] }
end
end
数组 arr 的所有元素大小必须相等，但不要求 arr.size = arr.first.size.
例子
arr = [
[ 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, 38, 39, 40],
[41, 42, 43, 44, 45, 46, 47, 48, 49, 50],
[51, 52, 53, 54, 55, 56, 57, 58, 59, 60],
[61, 62, 63, 64, 65, 66, 67, 68, 69, 70],
[71, 72, 73, 74, 75, 76, 77, 78, 79, 80],
[81, 82, 83, 84, 85, 86, 87, 88, 89, 90],
[91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
]
diagonals(arr, 4, 4)
#=> [[56, 67, 78, 89, 100, 1, 12, 23, 34],
# [54, 63, 72, 81, 9, 18, 27, 36]]
说明
假设
arr = (1..16).each_slice(4).to_a
#=> [[ 1, 2, 3, 4],
# [ 5, 6, 7, 8],
# [ 9, 10, 11, 12],
# [13, 14, 15, 16]]
row_idx = 2
col_idx = 1
步骤如下
a = Array.new(arr.size) { |i| Array.new(arr.first.size) { |j| [i,j] } }
#=> [[[0, 0], [0, 1], [0, 2], [0, 3]],
# [[1, 0], [1, 1], [1, 2], [1, 3]],
# [[2, 0], [2, 1], [2, 2], [2, 3]],
# [[3, 0], [3, 1], [3, 2], [3, 3]]]
ncols = arr.first.size
#=> 4
sum_idx = row_idx+col_idx
#=> 3
diff_idx = row_idx-col_idx
#=> 1
a = Array.new(arr.size * arr.first.size) { |i| i.divmod(ncols) } - [[row_idx, col_idx]]
#=> [[0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [1, 1], [1, 2], [1, 3],
# [2, 0], [2, 2], [2, 3], [3, 0], [3, 1], [3, 2], [3, 3]]
Select 并对通过 [row_idx, col_idx].
的左上角到右下角的对角线位置 [r, c] 进行排序
b = a.select { |r,c| r-c == diff_idx }
#=> [[1, 0], [3, 2]]
c = b.sort_by { |r,_| [r > row_idx ? 0:1 , r] }
#=> [[3, 2], [1, 0]]
Select 并对通过 [row_idx, col_idx].
的右上角左下角对角线上的位置 [r, c] 进行排序
d = a.select { |r,c| r+c == sum_idx }
#=> [[0, 3], [1, 2], [3, 0]]
e = d.sort_by { |r,c| [r > row_idx ? 0:1 , r] }
#=> [[3, 0], [0, 3], [1, 2]]
[c, e].map { |f| f.map { |r,c| arr[r][c] }
#=> [c, e].map { |f| f.map { |r,c| arr[r][c] } }
#=> [[15, 5], [13, 4, 7]]
我应用了@OmG 提供的逻辑。不确定效率如何。
def Whosebug(matrixSize, *args)
pos, obstacles = *args
chess = (1..(matrixSize * matrixSize)).each_slice(matrixSize).to_a
obstacles.each do |l| chess[l[0]][l[1]] = '_' end
row, col = pos[:row] - 1, pos[:col] - 1
chess[row][col] = '♙'
directions = [[],[],[],[],[],[],[],[]]
(1...matrixSize).each do |l|
directions[0] << chess[row + l][col + l] if (row + l) < matrixSize && (col + l) < chess_size
directions[1] << chess[row - l][col - l] if (row - l) >= 0 && (col - l) >= 0
directions[2] << chess[row + l][col - l] if (row + l) < matrixSize && (col - l) >= 0
directions[3] << chess[row - l][col + l] if (row - l) >= 0 && (col + l) < matrixSize
directions[4] << chess[row + l][col] if row + l < matrixSize
directions[5] << chess[row - l][col] if row - l >= 0
directions[6] << chess[row][col + l] if col + l < matrixSize
directions[7] << chess[row][col - l] if col - l >= 0
end
end
Whosebug(5, 3, {row: 4, col: 3}, [[4,4],[3,1],[1,2]] )
我刚刚从 OP 发表的评论中得知我解决了错误的问题，尽管事实上 OP 的问题看起来很清楚，尤其是示例，并且与我的解释一致。我将把这个解决方案留给以下问题：“给定一个数组 arr，使得 Matrix(*arr) 是一个 NxM 矩阵，矩阵位置 i,j，return 一个数组 [d,a]，其中元素 d 和 a 是通过 [d,a] 但不包括 [d,a] 的对角线和反对角线上的元素，并且每个元素都旋转，以便行索引如果 i < arr.size-1，第一个元素是 i+1，否则是 0。
以下方法使用 Matrix class.
中的方法
代码
require 'matrix'
def diagonals(arr, row_idx, col_idx)
[diag(arr, row_idx, col_idx),
diag(arr.map(&:reverse).transpose, arr.first.size-1-col_idx, row_idx)]
end
def diag(arr, row_idx, col_idx)
nrows, ncols = arr.size, arr.first.size
lr = [ncols-col_idx, nrows-row_idx].min - 1
ul = [col_idx, row_idx].min
m = Matrix[*arr]
[*m.minor(row_idx+1, lr, col_idx+1, lr).each(:diagonal).to_a,
*m.minor(row_idx-ul, ul, col_idx-ul, ul).each(:diagonal).to_a]
end
例子
arr = [
[ 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, 38, 39, 40],
[41, 42, 43, 44, 45, 46, 47, 48, 49, 50],
[51, 52, 53, 54, 55, 56, 57, 58, 59, 60],
[61, 62, 63, 64, 65, 66, 67, 68, 69, 70],
[71, 72, 73, 74, 75, 76, 77, 78, 79, 80],
[81, 82, 83, 84, 85, 86, 87, 88, 89, 90],
[91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
]
diagonals arr, 4, 4
#=> [[56, 67, 78, 89, 100, 1, 12, 23, 34], [54, 63, 72, 81, 9, 18, 27, 36]]
diagonals arr, 4, 5
#=> [[57, 68, 79, 90, 2, 13, 24, 35], [55, 64, 73, 82, 91, 10, 19, 28, 37]]
diagonals arr, 0, 9
#=> [[], [19, 28, 37, 46, 55, 64, 73, 82, 91]]
说明
假设数组和目标位置如下。
arr = (1..30).each_slice(6).to_a
#=> [[ 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]]
row_idx = 2
col_idx = 3
注arr[2][3] #=> 16。我们通过计算两个子矩阵的对角线得到负斜率的对角线：
[[23, 24],
[29, 30]]
和
[[2, 3],
[8, 9]]
给我们
[*[23, 30], *[2, 9]]
#=> [23, 30, 2, 9]
为了获得另一条对角线，我们将数组逆时针旋转 90 度，调整 row_idx 和 col_idx 并重复上述过程。
arr.map(&:reverse).transpose
#=> [[6, 12, 18, 24, 30],
# [5, 11, 17, 23, 29],
# [4, 10, 16, 22, 28],
# [3, 9, 15, 21, 27],
# [2, 8, 14, 20, 26],
# [1, 7, 13, 19, 25]]
ncols = arr.first.size
#=> 6
row_idx, col_idx = ncols-1-col_idx, row_idx
#=> [2, 2]
我们现在从矩阵 minors 中提取对角线
[[21, 27],
[20, 26]]
和
[[6, 12],
[5, 11]]
获取第二条对角线：
[21, 26, 6, 11]
@CarySwoveland 看来@Jamy 正在处理来自 hackerrank queens-attack 的另一个问题。
这个问题很难，因为我们的想法是从一开始就不要创建矩阵。也就是说，测试用例变得非常大，因此 space 复杂性将成为一个问题。
我已经更改了我的实现，但仍然因为超时问题而失败（这是因为测试用例变得非常大）。我不确定如何提高性能。
在我展示代码之前。让我用插图解释一下我想做什么：
这是我们的棋：
---------------------------
| 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 |
---------------------------
这是我们的女王所在的地方：queen[2][3]
---------------------------
| 1 2 3 4 5 |
| 6 7 8 9 10 |
| 11 12 13 ♙ 15 |
| 16 17 18 19 20 |
| 21 22 23 24 25 |
---------------------------
女王可以攻击所有8个方向。即：
horizontal(x2):
1. from queen position to left : [13, 12, 11]
2. from queen position to right : [15]
vertical(x2):
1. from queen position to top : [9, 4]
2. from queen position to bottom : [19, 24]
diagonal(x2):
1. from queen position to bottom-right : [20]
2. from queen position to top-left : [8, 2]
diagonal(x2):
1. from queen position to bottom-left : [18, 22]
2. from queen position to top-right : [10]
因为这8条路径内没有任何障碍物，所以女王一共可以攻击14次。
假设我们有一些障碍：
---------------------------
| 1 2 3 4 5 |
| 6 7 x 9 10 |
| 11 x 13 ♙ 15 |
| 16 17 18 19 x |
| 21 x 23 x 25 |
---------------------------
现在女王总共可以攻击7次：[13, 18, 19, 15, 10, 9, 4]
代码
MAXI = 10 ** 5
def queens_attack(size, number_of_obstacles, queen_pos, obstacles)
# exit the function if...
# size is negative or more than MAXI. Note MAXI has constraint shown in hackerrank
return if size < 0 || size > MAXI
# the obstacles is negative or more than the MAXI
return if number_of_obstacles < 0 || number_of_obstacles > MAXI
# the queen's position is outside of our chess dimension
return if queen_pos[:row] < 1 || queen_pos[:row] > size
return if queen_pos[:col] < 1 || queen_pos[:col] > size
# the queen's pos is the same as one of the obstacles
return if [[queen_pos[:row], queen_pos[:col]]] - obstacles == []
row, col = queen_pos[:row], queen_pos[:col]
# variable to increment how many places the queen can attack
attacks = 0
# the queen can attack on all directions:
# horizontals, verticals and both diagonals. So let us create pointers
# for each direction. Once the obstacle exists in the path, make the
# pointer[i] set to true
pointers = Array.new(8, false)
(1..size).lazy.each do |i|
# this is the diagonal from queen's pos to bottom-right
if row + i <= size && col + i <= size && !pointers[0]
# set it to true if there is no obstacle in the current [row + i, col + i]
pointers[0] = true unless [[row + i, col + i]] - obstacles != []
# now we know the queen can attack this pos
attacks += 1 unless pointers[0]
end
# this is diagonal from queen's pos to top-left
if row - i > 0 && col - i > 0 && !pointers[1]
# set it to true if there is no obstacle in the current [row - i, col - i]
pointers[1] = true unless [[row - i, col - i]] - obstacles != []
# now we know the queen can attack this pos
attacks += 1 unless pointers[1]
end
# this is diagonal from queen's pos to bottom-left
if row + i <= size && col - i > 0 && !pointers[2]
pointers[2] = true unless [[row + i, col - i]] - obstacles != []
attacks += 1 unless pointers[2]
end
# this is diagonal from queen's pos to top-right
if row - i > 0 && col + i <= size && !pointers[3]
pointers[3] = true unless [[row - i, col + i]] - obstacles != []
attacks += 1 unless pointers[3]
end
# this is verticle from queen's pos to bottom
if row + i <=size && !pointers[4]
pointers[4] = true unless [[row + i, col]] - obstacles != []
attacks += 1 unless pointers[4]
end
# this is verticle from queen's pos to top
if row - i > 0 && !pointers[5]
pointers[5] = true unless [[row - i, col]] - obstacles != []
attacks += 1 unless pointers[5]
end
# this is horizontal from queen's pos to right
if col + i <= size && !pointers[6]
pointers[6] = true unless [[row, col + i]] - obstacles != []
attacks += 1 unless pointers[6]
end
# this is horizontal from queen's pos to left
if col - i > 0 && !pointers[7]
pointers[7] = true unless [[row, col - i]] - obstacles != []
attacks += 1 unless pointers[7]
end
end
p attacks
end
问题
现在的问题是，我不知道为什么我的代码会出现来自 hackerrank 的超时错误。我确实知道它是因为测试用例，其中国际象棋的尺寸可以是 10,000 X 10,000。但是不知道我缺少什么约束。
这是 Hackerrank Queen's attack 问题的解决方案。
代码
def count_moves(n, obs, qrow, qcol)
qdiff = qrow-qcol
qsum = qrow+qcol
l = u = -1
r = d = n
ul = qdiff >= 0 ? qrow-qcol-1 : -1
dr = qdiff >= 0 ? n : qrow+n-qcol
ur = qsum < n ? -1 : qrow-n+qcol
dl = qsum < n ? qrow+qcol+1 : n
obs.uniq.each do |i,j|
case i <=> qrow
when -1 # up
case j <=> qcol
when -1 # up-left
ul = [ul,i].max
when 0 # up same col
u = [u,i].max
when 1 # up-right
ur = [ur,i].max
end
when 0 # same row
j < qcol ? (l = [l,j].max) : r = [r,j].min
else # down
case j <=> qcol
when -1 # down-left
dl = [dl,i].min
when 0 # down same col
d = [d,i].min
when 1 # down-right
dr = [dr,i].min
end
end
end
r + dl + d + dr - l - ul -u - ur - 8
end
示例
假设棋盘有 9 行和列，皇后的位置用字符 q 表示，每个障碍物用字母 o 表示。所有其他位置均由字母 x 表示。我们看到女王有 16 可能的移动（7 上下，6 左右，1 从左上到右下对角线和 [= 27=] 在右上角到左下角的对角线上。
arr = [
%w| x x x x x x x x x |, # 0
%w| o x x x x x x x x |, # 1
%w| x o x x x x x x x |, # 2
%w| x x o x x x x x o |, # 3
%w| x x x o x x x x x |, # 4
%w| x x x x x x o x x |, # 5
%w| o o x x x q x x x |, # 6
%w| x x x x x x o x x |, # 7
%w| x x x x x o x x x | # 8
# 0 1 2 3 4 5 6 7 8
]
qrow = qcol = nil
obs = []
n = arr.size
arr.each_with_index do |a,i|
a.each_with_index do |c,j|
case c
when 'o'
obs << [i,j]
when 'q'
qrow=i
qcol=j
end
end
end
qrow
#=> 6
qcol
#=> 5
obs
#=> [[1, 0], [2, 1], [3, 2], [3, 8], [4, 3], [5, 6], [6, 0], [6, 1], [7, 6], [8, 5]]
count_moves(n, obs, qrow, qcol)
#=> 16
说明
l是皇后行中小于皇后列索引的障碍物的最大列索引；r是大于皇后列索引的皇后区障碍物的最小列索引；u是queen's column中小于queen's row index的最大最大行索引；d是皇后列中大于皇后行索引的障碍物的最小行索引；ul是皇后左上角到右下角对角线上小于皇后行索引的障碍物的最大行索引；dr是皇后左上角到右下角对角线上障碍物的最小行索引，大于皇后的行索引；ur 是皇后从右上到左下对角线上小于皇后行索引的障碍物的最大行索引；和dl 是皇后从右上角到左下角的对角线上障碍物的最小行索引，大于皇后的行索引。
对于上面的示例，在考虑障碍物之前，这些变量设置为以下值。
l = 0
r = 9
ul = 0
u = -1
ur = 2
dl = 9
d = 9
dr = 9
请注意，如果皇后有行和列索引 qrow 和 qcol，
i - j = qrow - qcol 代表皇后左上角到右下角的所有位置 [i, j]；和i + j = grow + gcol 所有位置 [i, j] 在女王的右上角到左下角的对角线上
然后我们遍历所有（唯一的）障碍物，确定每个障碍物是在皇后的行、皇后的列还是皇后的对角线之一，然后用它的行或列索引，如果它比之前最近的位置 "closer" 到女王。
例如，如果障碍物在皇后的行中并且其列索引j小于皇后的列索引，则进行以下计算：
l = [l, j].max
类似地，如果障碍物位于皇后的左上角到右下角的对角线上，并且其行索引 i 小于皇后的行索引，则计算为：
ul = [ul, i].max
考虑到上述示例中的所有障碍后，变量具有以下值。
l #=> 1
r #=> 9
ul #=> 4
u #=> -1
ur #=> 5
dl #=> 9
d #=> 8
dr #=> 7
最后，我们计算女王可以移动到的方格总数。
qcol - l - 1 + # left
r - qcol - 1 + # right
u - qrow - 1 + # up
grow - d - 1 + # down
ul - qrow - 1 + # up-left
ur - qrow - 1 + # up-right
qrow - dl - 1 + # down-left
qrow - dr - 1 # down-right
简化为
r + dl + d + dr - l - ul -u - ur - 8
#=> 9 + 9 + 8 + 7 - 1 - 4 + 1 - 5 - 8 => 16
假设我有一个包含以下数据的 10x10 矩阵：
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 38 39 40
41 42 43 44 _ 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
我的位置在[4][4]。如何列出此位置的对角线值？
例如，预期结果为：
[56, 67, 78, 89, 100, 1, 12, 23, 34]
[54, 63, 72, 81, 9, 18, 27, 36]
我目前的解决方案
def next?(index, row, size)
(((row + index) % size) + 1 ) % size
end
(1...chess_size).each do |l|
next_el, curr_el = next?(l, row, chess_size), (row + l) % chess_size
# this gets me the first diagnonal. Note that it prints out wrong value
tmp[0] << chess[curr_el][curr_el]
# this gets me the values from current row below to up
tmp[1] << chess[(row + l) % chess_size][row]
tmp[2] << chess[-l][l]
tmp[3] << chess[row][(row + l) % chess_size]
end
我们的矩阵将始终具有相同的行数和列数。
通常要从 i 和 j 获取对角线值，您可以同时迭代 i 和 j，最多其中一个是零。因此，主对角线是 (i-1, j-1), (i-2, j-2), ... 到 i, j >= 0 和 (i + 1, j + 1), (i +2, j + 2), ... 到 i, j <= n。因为反对角线是 (i - 1, j + 1), (i - 2, j + 2), ... 到 i >= 0 和 j <= n，并且 (i + 1, j-1), (i + 2, j - 2), ... 到 i <= n 和 j >= 0.
我刚刚从 OP 发表的评论中得知我解决了错误的问题，尽管事实上 OP 的问题看起来很清楚，尤其是示例，并且与我的解释一致。我将把这个解决方案留给以下问题：“给定一个数组 arr，使得 Matrix(*arr) 是一个 NxM 矩阵，矩阵位置 i,j，return 一个数组 [d,a]，其中元素 d 和 a 是通过 [d,a] 但不包括 [d,a] 的对角线和反对角线上的元素，并且每个元素都旋转，以便行索引如果 i < arr.size-1，第一个元素是 i+1，否则是 0。
代码
def diagonals(arr, row_idx, col_idx)
ncols = arr.first.size
sum_idx = row_idx+col_idx
diff_idx = row_idx-col_idx
a = Array.new(arr.size * arr.first.size) { |i| i.divmod(ncols) } -[[row_idx, col_idx]]
[a.select { |r,c| r-c == diff_idx }, a.select { |r,c| r+c == sum_idx }].
map do |b| b.sort_by { |r,_| [r > row_idx ? 0:1 , r] }.
map { |r,c| arr[r][c] }
end
end
数组 arr 的所有元素大小必须相等，但不要求 arr.size = arr.first.size.
例子
arr = [
[ 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, 38, 39, 40],
[41, 42, 43, 44, 45, 46, 47, 48, 49, 50],
[51, 52, 53, 54, 55, 56, 57, 58, 59, 60],
[61, 62, 63, 64, 65, 66, 67, 68, 69, 70],
[71, 72, 73, 74, 75, 76, 77, 78, 79, 80],
[81, 82, 83, 84, 85, 86, 87, 88, 89, 90],
[91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
]
diagonals(arr, 4, 4)
#=> [[56, 67, 78, 89, 100, 1, 12, 23, 34],
# [54, 63, 72, 81, 9, 18, 27, 36]]
说明
假设
arr = (1..16).each_slice(4).to_a
#=> [[ 1, 2, 3, 4],
# [ 5, 6, 7, 8],
# [ 9, 10, 11, 12],
# [13, 14, 15, 16]]
row_idx = 2
col_idx = 1
步骤如下
a = Array.new(arr.size) { |i| Array.new(arr.first.size) { |j| [i,j] } }
#=> [[[0, 0], [0, 1], [0, 2], [0, 3]],
# [[1, 0], [1, 1], [1, 2], [1, 3]],
# [[2, 0], [2, 1], [2, 2], [2, 3]],
# [[3, 0], [3, 1], [3, 2], [3, 3]]]
ncols = arr.first.size
#=> 4
sum_idx = row_idx+col_idx
#=> 3
diff_idx = row_idx-col_idx
#=> 1
a = Array.new(arr.size * arr.first.size) { |i| i.divmod(ncols) } - [[row_idx, col_idx]]
#=> [[0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [1, 1], [1, 2], [1, 3],
# [2, 0], [2, 2], [2, 3], [3, 0], [3, 1], [3, 2], [3, 3]]
Select 并对通过 [row_idx, col_idx].
[r, c] 进行排序
b = a.select { |r,c| r-c == diff_idx }
#=> [[1, 0], [3, 2]]
c = b.sort_by { |r,_| [r > row_idx ? 0:1 , r] }
#=> [[3, 2], [1, 0]]
Select 并对通过 [row_idx, col_idx].
[r, c] 进行排序
d = a.select { |r,c| r+c == sum_idx }
#=> [[0, 3], [1, 2], [3, 0]]
e = d.sort_by { |r,c| [r > row_idx ? 0:1 , r] }
#=> [[3, 0], [0, 3], [1, 2]]
[c, e].map { |f| f.map { |r,c| arr[r][c] }
#=> [c, e].map { |f| f.map { |r,c| arr[r][c] } }
#=> [[15, 5], [13, 4, 7]]
我应用了@OmG 提供的逻辑。不确定效率如何。
def Whosebug(matrixSize, *args)
pos, obstacles = *args
chess = (1..(matrixSize * matrixSize)).each_slice(matrixSize).to_a
obstacles.each do |l| chess[l[0]][l[1]] = '_' end
row, col = pos[:row] - 1, pos[:col] - 1
chess[row][col] = '♙'
directions = [[],[],[],[],[],[],[],[]]
(1...matrixSize).each do |l|
directions[0] << chess[row + l][col + l] if (row + l) < matrixSize && (col + l) < chess_size
directions[1] << chess[row - l][col - l] if (row - l) >= 0 && (col - l) >= 0
directions[2] << chess[row + l][col - l] if (row + l) < matrixSize && (col - l) >= 0
directions[3] << chess[row - l][col + l] if (row - l) >= 0 && (col + l) < matrixSize
directions[4] << chess[row + l][col] if row + l < matrixSize
directions[5] << chess[row - l][col] if row - l >= 0
directions[6] << chess[row][col + l] if col + l < matrixSize
directions[7] << chess[row][col - l] if col - l >= 0
end
end
Whosebug(5, 3, {row: 4, col: 3}, [[4,4],[3,1],[1,2]] )
我刚刚从 OP 发表的评论中得知我解决了错误的问题，尽管事实上 OP 的问题看起来很清楚，尤其是示例，并且与我的解释一致。我将把这个解决方案留给以下问题：“给定一个数组 arr，使得 Matrix(*arr) 是一个 NxM 矩阵，矩阵位置 i,j，return 一个数组 [d,a]，其中元素 d 和 a 是通过 [d,a] 但不包括 [d,a] 的对角线和反对角线上的元素，并且每个元素都旋转，以便行索引如果 i < arr.size-1，第一个元素是 i+1，否则是 0。
以下方法使用 Matrix class.
中的方法代码
require 'matrix'
def diagonals(arr, row_idx, col_idx)
[diag(arr, row_idx, col_idx),
diag(arr.map(&:reverse).transpose, arr.first.size-1-col_idx, row_idx)]
end
def diag(arr, row_idx, col_idx)
nrows, ncols = arr.size, arr.first.size
lr = [ncols-col_idx, nrows-row_idx].min - 1
ul = [col_idx, row_idx].min
m = Matrix[*arr]
[*m.minor(row_idx+1, lr, col_idx+1, lr).each(:diagonal).to_a,
*m.minor(row_idx-ul, ul, col_idx-ul, ul).each(:diagonal).to_a]
end
例子
arr = [
[ 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, 38, 39, 40],
[41, 42, 43, 44, 45, 46, 47, 48, 49, 50],
[51, 52, 53, 54, 55, 56, 57, 58, 59, 60],
[61, 62, 63, 64, 65, 66, 67, 68, 69, 70],
[71, 72, 73, 74, 75, 76, 77, 78, 79, 80],
[81, 82, 83, 84, 85, 86, 87, 88, 89, 90],
[91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
]
diagonals arr, 4, 4
#=> [[56, 67, 78, 89, 100, 1, 12, 23, 34], [54, 63, 72, 81, 9, 18, 27, 36]]
diagonals arr, 4, 5
#=> [[57, 68, 79, 90, 2, 13, 24, 35], [55, 64, 73, 82, 91, 10, 19, 28, 37]]
diagonals arr, 0, 9
#=> [[], [19, 28, 37, 46, 55, 64, 73, 82, 91]]
说明
假设数组和目标位置如下。
arr = (1..30).each_slice(6).to_a
#=> [[ 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]]
row_idx = 2
col_idx = 3
注arr[2][3] #=> 16。我们通过计算两个子矩阵的对角线得到负斜率的对角线：
[[23, 24],
[29, 30]]
和
[[2, 3],
[8, 9]]
给我们
[*[23, 30], *[2, 9]]
#=> [23, 30, 2, 9]
为了获得另一条对角线，我们将数组逆时针旋转 90 度，调整 row_idx 和 col_idx 并重复上述过程。
arr.map(&:reverse).transpose
#=> [[6, 12, 18, 24, 30],
# [5, 11, 17, 23, 29],
# [4, 10, 16, 22, 28],
# [3, 9, 15, 21, 27],
# [2, 8, 14, 20, 26],
# [1, 7, 13, 19, 25]]
ncols = arr.first.size
#=> 6
row_idx, col_idx = ncols-1-col_idx, row_idx
#=> [2, 2]
我们现在从矩阵 minors 中提取对角线
[[21, 27],
[20, 26]]
和
[[6, 12],
[5, 11]]
获取第二条对角线：
[21, 26, 6, 11]
@CarySwoveland 看来@Jamy 正在处理来自 hackerrank queens-attack 的另一个问题。
这个问题很难，因为我们的想法是从一开始就不要创建矩阵。也就是说，测试用例变得非常大，因此 space 复杂性将成为一个问题。
我已经更改了我的实现，但仍然因为超时问题而失败（这是因为测试用例变得非常大）。我不确定如何提高性能。
在我展示代码之前。让我用插图解释一下我想做什么：
这是我们的棋：
---------------------------
| 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 |
---------------------------
这是我们的女王所在的地方：queen[2][3]
---------------------------
| 1 2 3 4 5 |
| 6 7 8 9 10 |
| 11 12 13 ♙ 15 |
| 16 17 18 19 20 |
| 21 22 23 24 25 |
---------------------------
女王可以攻击所有8个方向。即：
horizontal(x2):
1. from queen position to left : [13, 12, 11]
2. from queen position to right : [15]
vertical(x2):
1. from queen position to top : [9, 4]
2. from queen position to bottom : [19, 24]
diagonal(x2):
1. from queen position to bottom-right : [20]
2. from queen position to top-left : [8, 2]
diagonal(x2):
1. from queen position to bottom-left : [18, 22]
2. from queen position to top-right : [10]
因为这8条路径内没有任何障碍物，所以女王一共可以攻击14次。
假设我们有一些障碍：
---------------------------
| 1 2 3 4 5 |
| 6 7 x 9 10 |
| 11 x 13 ♙ 15 |
| 16 17 18 19 x |
| 21 x 23 x 25 |
---------------------------
现在女王总共可以攻击7次：[13, 18, 19, 15, 10, 9, 4]
代码
MAXI = 10 ** 5
def queens_attack(size, number_of_obstacles, queen_pos, obstacles)
# exit the function if...
# size is negative or more than MAXI. Note MAXI has constraint shown in hackerrank
return if size < 0 || size > MAXI
# the obstacles is negative or more than the MAXI
return if number_of_obstacles < 0 || number_of_obstacles > MAXI
# the queen's position is outside of our chess dimension
return if queen_pos[:row] < 1 || queen_pos[:row] > size
return if queen_pos[:col] < 1 || queen_pos[:col] > size
# the queen's pos is the same as one of the obstacles
return if [[queen_pos[:row], queen_pos[:col]]] - obstacles == []
row, col = queen_pos[:row], queen_pos[:col]
# variable to increment how many places the queen can attack
attacks = 0
# the queen can attack on all directions:
# horizontals, verticals and both diagonals. So let us create pointers
# for each direction. Once the obstacle exists in the path, make the
# pointer[i] set to true
pointers = Array.new(8, false)
(1..size).lazy.each do |i|
# this is the diagonal from queen's pos to bottom-right
if row + i <= size && col + i <= size && !pointers[0]
# set it to true if there is no obstacle in the current [row + i, col + i]
pointers[0] = true unless [[row + i, col + i]] - obstacles != []
# now we know the queen can attack this pos
attacks += 1 unless pointers[0]
end
# this is diagonal from queen's pos to top-left
if row - i > 0 && col - i > 0 && !pointers[1]
# set it to true if there is no obstacle in the current [row - i, col - i]
pointers[1] = true unless [[row - i, col - i]] - obstacles != []
# now we know the queen can attack this pos
attacks += 1 unless pointers[1]
end
# this is diagonal from queen's pos to bottom-left
if row + i <= size && col - i > 0 && !pointers[2]
pointers[2] = true unless [[row + i, col - i]] - obstacles != []
attacks += 1 unless pointers[2]
end
# this is diagonal from queen's pos to top-right
if row - i > 0 && col + i <= size && !pointers[3]
pointers[3] = true unless [[row - i, col + i]] - obstacles != []
attacks += 1 unless pointers[3]
end
# this is verticle from queen's pos to bottom
if row + i <=size && !pointers[4]
pointers[4] = true unless [[row + i, col]] - obstacles != []
attacks += 1 unless pointers[4]
end
# this is verticle from queen's pos to top
if row - i > 0 && !pointers[5]
pointers[5] = true unless [[row - i, col]] - obstacles != []
attacks += 1 unless pointers[5]
end
# this is horizontal from queen's pos to right
if col + i <= size && !pointers[6]
pointers[6] = true unless [[row, col + i]] - obstacles != []
attacks += 1 unless pointers[6]
end
# this is horizontal from queen's pos to left
if col - i > 0 && !pointers[7]
pointers[7] = true unless [[row, col - i]] - obstacles != []
attacks += 1 unless pointers[7]
end
end
p attacks
end
问题
现在的问题是，我不知道为什么我的代码会出现来自 hackerrank 的超时错误。我确实知道它是因为测试用例，其中国际象棋的尺寸可以是 10,000 X 10,000。但是不知道我缺少什么约束。
这是 Hackerrank Queen's attack 问题的解决方案。
代码
def count_moves(n, obs, qrow, qcol)
qdiff = qrow-qcol
qsum = qrow+qcol
l = u = -1
r = d = n
ul = qdiff >= 0 ? qrow-qcol-1 : -1
dr = qdiff >= 0 ? n : qrow+n-qcol
ur = qsum < n ? -1 : qrow-n+qcol
dl = qsum < n ? qrow+qcol+1 : n
obs.uniq.each do |i,j|
case i <=> qrow
when -1 # up
case j <=> qcol
when -1 # up-left
ul = [ul,i].max
when 0 # up same col
u = [u,i].max
when 1 # up-right
ur = [ur,i].max
end
when 0 # same row
j < qcol ? (l = [l,j].max) : r = [r,j].min
else # down
case j <=> qcol
when -1 # down-left
dl = [dl,i].min
when 0 # down same col
d = [d,i].min
when 1 # down-right
dr = [dr,i].min
end
end
end
r + dl + d + dr - l - ul -u - ur - 8
end
示例
假设棋盘有 9 行和列，皇后的位置用字符 q 表示，每个障碍物用字母 o 表示。所有其他位置均由字母 x 表示。我们看到女王有 16 可能的移动（7 上下，6 左右，1 从左上到右下对角线和 [= 27=] 在右上角到左下角的对角线上。
arr = [
%w| x x x x x x x x x |, # 0
%w| o x x x x x x x x |, # 1
%w| x o x x x x x x x |, # 2
%w| x x o x x x x x o |, # 3
%w| x x x o x x x x x |, # 4
%w| x x x x x x o x x |, # 5
%w| o o x x x q x x x |, # 6
%w| x x x x x x o x x |, # 7
%w| x x x x x o x x x | # 8
# 0 1 2 3 4 5 6 7 8
]
qrow = qcol = nil
obs = []
n = arr.size
arr.each_with_index do |a,i|
a.each_with_index do |c,j|
case c
when 'o'
obs << [i,j]
when 'q'
qrow=i
qcol=j
end
end
end
qrow
#=> 6
qcol
#=> 5
obs
#=> [[1, 0], [2, 1], [3, 2], [3, 8], [4, 3], [5, 6], [6, 0], [6, 1], [7, 6], [8, 5]]
count_moves(n, obs, qrow, qcol)
#=> 16
说明
l是皇后行中小于皇后列索引的障碍物的最大列索引；r是大于皇后列索引的皇后区障碍物的最小列索引；u是queen's column中小于queen's row index的最大最大行索引；d是皇后列中大于皇后行索引的障碍物的最小行索引；ul是皇后左上角到右下角对角线上小于皇后行索引的障碍物的最大行索引；dr是皇后左上角到右下角对角线上障碍物的最小行索引，大于皇后的行索引；ur是皇后从右上到左下对角线上小于皇后行索引的障碍物的最大行索引；和dl是皇后从右上角到左下角的对角线上障碍物的最小行索引，大于皇后的行索引。
对于上面的示例，在考虑障碍物之前，这些变量设置为以下值。
l = 0
r = 9
ul = 0
u = -1
ur = 2
dl = 9
d = 9
dr = 9
请注意，如果皇后有行和列索引 qrow 和 qcol，
i - j = qrow - qcol代表皇后左上角到右下角的所有位置[i, j]；和i + j = grow + gcol所有位置[i, j]在女王的右上角到左下角的对角线上
然后我们遍历所有（唯一的）障碍物，确定每个障碍物是在皇后的行、皇后的列还是皇后的对角线之一，然后用它的行或列索引，如果它比之前最近的位置 "closer" 到女王。
例如，如果障碍物在皇后的行中并且其列索引j小于皇后的列索引，则进行以下计算：
l = [l, j].max
类似地，如果障碍物位于皇后的左上角到右下角的对角线上，并且其行索引 i 小于皇后的行索引，则计算为：
ul = [ul, i].max
考虑到上述示例中的所有障碍后，变量具有以下值。
l #=> 1
r #=> 9
ul #=> 4
u #=> -1
ur #=> 5
dl #=> 9
d #=> 8
dr #=> 7
最后，我们计算女王可以移动到的方格总数。
qcol - l - 1 + # left
r - qcol - 1 + # right
u - qrow - 1 + # up
grow - d - 1 + # down
ul - qrow - 1 + # up-left
ur - qrow - 1 + # up-right
qrow - dl - 1 + # down-left
qrow - dr - 1 # down-right
简化为
r + dl + d + dr - l - ul -u - ur - 8
#=> 9 + 9 + 8 + 7 - 1 - 4 + 1 - 5 - 8 => 16