2D матрица, найти все числа на прямой линии между двумя числами

Question

Если задана квадратная двумерная матрица произвольного размера, как найти все числа на пути между двумя выбранными числами. Например:

    |  1 |  2 |  3 |  4 |
    |----+----+----+----|
    |  5 |  6 |  7 |  8 |
    |----+----+----+----|
    |  9 | 10 | 11 | 12 |
    |----+----+----+----|
    | 13 | 14 | 15 | 16 |

• для 6,16 = {11}
• для 3,15 = {7,11}
• для 9,2 = { }
• для 4,13 = {7,10}
• для 8,10 = {}
• для 12,9 = {11,10}
• et c.

Answer 1

Работа в координатах X / Y (они могут быть вычислены из значений с использованием целочисленного деления и moudulo, если необходимо )

Рассчитать GCD (наибольший общий делитель) различий по горизонтали и по вертикали.

int gcd (int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd (b, a % b);
}

dx = abs(x2 - x1);
dy = abs(y2 - y1);
gc = gcd(dx, dy);

Количество внутренних целых точек составляет n = gc-1, поэтому вы можете сделать простые l oop

xstep = (x2 - x1) / gc;
ystep = (y2 - y1) / gc;  //both are integer values
for (i = 1; i < gc; i++) {
   x = x1 + xstep * i;
   y = y1 + ystep * i;
}

Answer 2

РЕДАКТИРОВАТЬ : я сделал упрощенное предположение, что вы хотите перейти только к соседним ячейкам. В этом случае вы смотрите только на горизонтальные, вертикальные или диагональные (45 градусов) пути. Тем не менее, когда сетка становится больше, можно рассматривать прямые пути через центры ячеек, которые пропускают соседние ячейки. Например, 10 и 19 l ie между 1 и 28 на сетке размера 7 - пример, предоставленный MBo в его комментарии. Чтобы справиться с этими случаями, вам нужно будет включить Величайший общий делитель в определение размера шага, как указано MBo в его ответе .

. Просто вычислите строку и разница столбцов в позициях и шаге от первой ячейки ко второй.

Вот пример Java кода для иллюстрации:

static int[] gridCells(int size, int from, int to)
{
    int fromRow = (from-1) / size;
    int fromCol = (from-1) % size;

    int toRow = (to-1) / size;
    int toCol = (to-1) % size;

    int rowDiff = toRow - fromRow;
    int colDiff = toCol - fromCol;

    if(rowDiff == 0 || colDiff == 0 || Math.abs(rowDiff) == Math.abs(colDiff))
    {
        int maxStep = Math.max(Math.abs(rowDiff), Math.abs(colDiff));           
        if(maxStep > 1)
        {
            int rowStep = rowDiff / maxStep;
            int colStep = colDiff / maxStep;
            int[] cells = new int[maxStep-1];
            for(int i=0; i<cells.length; i++)           
                cells[i] = (fromRow + (i+1)*rowStep) * size + fromCol + ((i+1)*colStep) + 1;
            return cells;
        }
    }

    return new int[]{};
}

Тест:

for(int[] t : new int[][] {{5,5}, {6,16}, {3,15}, {9,2}, {4,13}, {8,10}, {12,9}})
    System.out.format("%s : %s%n", Arrays.toString(t), Arrays.toString(gridCells(4, t[0], t[1])));

Вывод:

[5, 5] : []
[6, 16] : [11]
[3, 15] : [7, 11]
[9, 2] : []
[4, 13] : [7, 10]
[8, 10] : []
[12, 9] : [11, 10]

Answer 3

Сначала давайте построим функцию для поиска позиции для любого числа в матрице n x n:

position(a) = ((a - 1) / n, (a - 1) % n)

Затем, учитывая 2 числа a и b, возьмем position(a) = (ax, ay) и position(b) = (bx, by).

• Если они находятся в одной строке, ax - bx = 0.
• Если они находятся в одном столбце, ay - by = 0.
• Если они находятся по диагонали друг от друга, abs(ax - bx) = abs(ay - by).

Просто оцените условия и напечатайте элементы в правильном порядке:

#include <bits/stdc++.h>
using namespace std;

int m[4][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};

int main(){
    int n = 4;
    while(true){
        int a, b;
        cin>>a>>b;                     //input elements
        int ax = (a - 1) % n, ay = (a - 1) / n;
        int bx = (b - 1) % n, by = (b - 1) / n;
        pair<int, int> p;

        int dx = bx - ax;
        int dy = by - ay;

        if(dx == 0 || dy == 0 || abs(dx) == abs(dy)) 
            p = make_pair(dx < 0? -1 : dx > 0, dy < 0? -1 : dy > 0);
        else continue;  //there isnt a path in this case

        while(true){
            ax += p.first; ay += p.second;
            if(ax != bx || ay != by) cout<<m[ay][ax]<<endl;
            else break;
        }
    }
}

Сложность: O ( n) , поскольку можно печатать не более n элементов.