Проверьте, если элемент 2D-сетки имеет общую диагональ, горизонталь или вертикаль с другим элементом - PullRequest
Новая
       27

Проверьте, если элемент 2D-сетки имеет общую диагональ, горизонталь или вертикаль с другим элементом

0 голосов
/ 15 октября 2018

Я работаю над проблемой n-queens и частично проверяю, угрожает ли другой ферзь королеве, чтобы определить хорошее состояние доски.

У меня есть двумерный массив, заполненный нулями, в этомНапример, 4x4: 

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Я случайным образом заполняю каждую строку одной королевой, в данном случае это 1: 

0 0 1 0
1 0 0 0 
1 0 0 0
0 0 0 1

Мне нужно проверить, сколько других фигур угрожают данномукусок.Королеве грозит опасность, если она делит горизонталь, диагональ или вертикаль с другой королевой.

Однако я не совсем уверен, как пройти массив по диагонали. 

int checkThreats(vector<vector<int> > board, int r, int c) {
    int threats = 0;
    // checks vertical and horizontal
    for (int i = 0; i < board.size(); i++) {
        if (board[i][c] == 1 || board[r][i] == 1) {
            threats++;
        }
    }
    // it will count itself as a threat, so less one
    threats--;
    return threats;
}

Этоалгоритм проверки по горизонтали и вертикали.Учитывая позицию на доске r, c, она проверяет, сколько королев существует в позициях слева, справа, вверх и вниз (в форме креста +).

Взять координату r, cиз 1, 0, проверенные позиции помечаются x, o, если существует угроза: 

x 0 1 0
o x x x
o 0 0 0
x 0 0 1

В этом случае threats == 1, поскольку мы не считаем исходныйposition.

Моя проблема - попытаться найти фигуры в форме x вдоль диагоналей.

Ответы [ 2 ]

0 голосов
/ 15 октября 2018

Путем проб и ошибок я смог заставить работать алгоритм.Вот петли для перемещения во всех направлениях: 

function check(arr, row, col) {
    for (i = 0; i < arr.size(); i++) {} // left/right can be iterated as normal
    for (i = 0; i < arr.size(); i++) {} // top/down can be the same
    // lower-right diagonal from (row, col)
    for (i = row+1, j = col+1; i < arr.size() && i < arr.size(); i++, j++) {}
    // upper-left diagonal from (row, col)
    for (i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {}
    // lower-left diagonal from (row, col)
    for (i = row-1, j = col+1; i >= 0 && j < arr.size(); i--, j++) {}
    // upper-right diagonal from (row, col)
    for (i = row+1, j = col-1; i < arr.size() && j >= 0; i++, j--) {}
}

Конечно, это работает только для квадратных массивов.

0 голосов
/ 15 октября 2018

Уловка с диагоналями заключается в том, что они имеют разную длину (общую и отдельную; учтите, что они составляют всего 3 квадрата, начиная с края или угла вашей доски, но 5 от середины).Эта нерегулярность усложняет их учет.

Одна из стратегий состоит в том, чтобы зацикливать (скажем) строки, рассматривая для каждого 0 (если это строка субъекта), 1 (если один отсутствует)) или 2 квадрата, которые находятся на диагонали в этом ряду.Индексы столбцов для проверки просто c0+(r-r0) и c0-(r-r0).

...