如何编写算法来查找给定点的所有对角线点？
如：
00 01 02 03 04 05
10 11 12 13 14 15
20 21 22 23 24 25
30 31 32 33 34 35
40 41 42 43 44 45
50 51 52 53 54 55
选择点 34 时，如何找到相邻的对角线点？(01,12,23,45,25,43,52(
00(01)02 03 04 05
10 11(12)13 14 15
20 21 22(23)24(25)
30 31 32 33 X 35
40 41 42(43)44(45)
50 51(52)53 54 55
由于我没有说明我使用的编程语言，所以我更喜欢伪代码或指令。
Ps：我不想要直接的代码赠品，因为我正在尝试通过遵循伪代码或说明来学习编码。
假设你的观点在(a，b(上。如果存在一个i整数，则给定的(c， d(点位于同一对角线上，因此
a + i =c 和 b + i = d或a + i = c 和 b - i = d
由于距离为i，因此可以执行以下操作：
for i <- 0, n - 1
if i <> a then
if (b - i) >= 0 and (b - i) < n then (i, b - i) is on the diagonal
if (b + i) >= 0 and (b + i) < n then (i, b + i) is on the diagonal
end if
end for
蛮力解决方案
在整个网格上编写一些简单的 for 循环。对角线上的任何点的斜率为 1，起点为 1
假设一个零索引的 N x N 框，x 从左到右增加，y 从上到下增加
values = list()
location = (3,4)
for y in 0 ..N-1:
for x in 0..N-1:
if (x, y) == location:
continue
slope = abs(y-location(0))/abs(x-location(1))
if slope == 1:
list.add( (y, x) )
更优化的解决方案
从位置坐标开始，然后向外扇动，同时增加和/或减少两个 x、y 点。该方法的棘手部分是当一个方向碰到边界时不要中断循环
我用 C# 为这个公认的答案 (https://stackoverflow.com/a/45896595/1566372( 编写了一个实现
public IEnumerable<(int i, int j)> GetDiagonalPoints(int a, int b, int n)
{
/*
for i <- 0, n - 1
if i <> a then
dist = Abs(i - a)
if (b - dist) >= 0 and (b - dist) < n then (i, b - dist) is on the diagonal
if (b + dist) >= 0 and (b + dist) < n then (i, b + dist) is on the diagonal
end if
end for
*/
for (int i = 0; i < n; i++)
{
if (i != a)
{
var dist = Math.Abs(i - a);
if ((b - dist) >= 0 && (b - dist) < n) yield return (i, b - dist);
if ((b + dist) < n) yield return (i, b + dist);
}
}
}
对我来说，编写代码本身比编写伪代码更容易......
N 是从零开始的矩阵的大小。
public static void diagonal(int N, int x, int y) {
int max = Collections.max(Arrays.asList(x, y, N - x, N - y));
for (int i = 1; i < max; i++) {
addIfValid(N, x + i, y + i);
addIfValid(N, x + i, y - i);
addIfValid(N, x - i, y + i);
addIfValid(N, x - i, y - i);
}
}
private static void addIfValid(int N, int i, int j) {
if (i >= 0 && i < N && j >= 0 && j < N) {
// collect the results in a list or process them in any way
System.out.println(i + ":" + j);
}
}
在Lajos Arpad回答的指导下，我做了一些更改以满足我的需求。
//point_given = (3,3)
//matrix = 5*4
/*
00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33
40 41 42 43
*/
x = 3 // x of given point
y = 3 // y of given point
N = 5 //row
M = 4 //col
//use row to iterate only
for i = 0 to N, i+1
//no diagonal point on same row of given point
if i <> x
//to check if y in bound of matrix col for the left and right diagonal
//used abs(x-i) to know how much value to add to y col
//e.g. 1 row up of x means the diagonal point y is 1 col left and 1 col right to given y
if((y-abs(x-i))>=0) then (i,y-abs(x-i)) is a diagonal point on left
endif
if((y+abs(x-i))<M) then (i,y+abs(x-i)) is a diagonal point on right
endif
endif
endfor
我写了一个基于@Rady解决方案的Python解决方案：https://stackoverflow.com/a/63219124/14726555
我还添加了代码来绘制任何大小的对角线，以便更容易理解此解决方案的工作原理以及它对生成对角线的用处。
def diag_iter(row, col, n):
for i in range(n):
if i != row:
dist = abs(i - row)
if 0 <= col - dist < n:
yield (i, col - dist)
if col + dist < n:
yield (i, col + dist)
def print_diag(row, col, n):
board = [['_'] * n for _ in range(n)]
board[row][col] = 'X'
for diag_row, diag_col in diag_iter(row, col, n):
board[diag_row][diag_col] = "X"
print(f"Board of size {n} with diagional starting at ({row}, {col})")
for row in board:
print(row)
print_diag(1, 1, 5)
print_diag(2, 2, 5)
print_diag(3, 4, 5)
print_diag(0, 3, 5)
"""
Board of size 5 with diagional starting at (1, 1)
['X', '_', 'X', '_', '_']
['_', 'X', '_', '_', '_']
['X', '_', 'X', '_', '_']
['_', '_', '_', 'X', '_']
['_', '_', '_', '_', 'X']
Board of size 5 with diagional starting at (2, 2)
['X', '_', '_', '_', 'X']
['_', 'X', '_', 'X', '_']
['_', '_', 'X', '_', '_']
['_', 'X', '_', 'X', '_']
['X', '_', '_', '_', 'X']
Board of size 5 with diagional starting at (3, 4)
['_', 'X', '_', '_', '_']
['_', '_', 'X', '_', '_']
['_', '_', '_', 'X', '_']
['_', '_', '_', '_', 'X']
['_', '_', '_', 'X', '_']
Board of size 5 with diagional starting at (0, 3)
['_', '_', '_', 'X', '_']
['_', '_', 'X', '_', 'X']
['_', 'X', '_', '_', '_']
['X', '_', '_', '_', '_']
['_', '_', '_', '_', '_']
"""