查找给定点的所有对角点的算法

Question

如何编写算法来找到给定点的所有对角线点？

如：

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：我不想直接赠送代码，因为我正在尝试按照伪代码或说明学习编码。

Answer 1

暴力破解

在整个网格上写一些简单的 for 循环。对角线上任意点的斜率为 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 点。该方法的棘手部分是当一个方向碰到边界时不中断循环

Answer 2

我自己写代码比伪代码更容易...

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);
    }
}

Answer 3

假设您的观点是 (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

Answer 4

按照 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

Answer 5

我用 C#

为这个已接受的答案 () 编写了一个实现

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);
                }
            }
        }

Answer 6

我写了一个Python解决方案基于@Rady解决方案：

我还添加了代码来绘制任意大小的对角线，以便更容易理解此解决方案为何有效以及它对生成对角线有何用处。

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', '_', '_', '_', '_']
['_', '_', '_', '_', '_']
"""

查找给定点的所有对角点的算法

Algorithm to find all diagonal point of a given point

algorithm

point

pseudocode

coordinate