LINUX.ORG.RU

Найти 3 или больше одинаковых элементов


0

0

Есть матрица достаточно большого размера и дан элемент с известными координатами (x.y).

Какие есть оптимальные алгоритмы чтобы найти все последовательности из 3 и более элементов стоящих с ним на одной вертикали, горизонтали, диагонали?

Я в принципе придумал как это можно сделать, но мне интересно как это делать правильно.

Поиск в гугле ничего не нашел, или я туплю. 8(

★★★★

Ответ на: комментарий от dmiceman

А можно поподробнее, я просто тоже думал в лоб решать, но вдруг мой лоб окажется тверже.

OxiD ★★★★
() автор топика
Ответ на: комментарий от OxiD

ну как бы там уже привязка к деталям.. проходим последовательно все четыре направления (широта, высота, две диагонали), сравниваем каждый элемент с предыдущим, увеличиваем счетчик при совпадении, сбрасываем при несовпадении. набралось три -- делаем с ними что надо. как бы особо вариантов тут нет. смысла в хитрых алгоритмах [в общем случае] -- тоже нет.

вот если есть какие-то предположения о структуре матрицы, типа того что вот в этом направлении оно встречаться может, а в этом нет -- ну тогда есть над чем подумать. а так..

dmiceman ★★★★★
()

Например для матрицы A(MxN) определяеш оператор Zх, выдающие матрицу X(M-1 x N), у которой x(i,j)=A(i,j)==A(i+1,j). Матрица ZхZхA будет содержать единицы в там, где в исходной три одинаковых по горизонтали. ZxZхZхA - там где четыре итд. Для вертикали и диагонали аналогично. Как оптимизировать - зависит от йазыга.

bugmaker ★★★★☆
()
Ответ на: комментарий от OxiD

нужен поиск одновременно по нескольким направлениям (вертикаль, горизонталь, две диагонали) или по отдельности? Нужно знать точное количество повторов или достаточно знать, что допустим более трёх?

bugmaker ★★★★☆
()
Ответ на: комментарий от bugmaker

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

В результате нужно удалить сразу все элементы которые стояли на одной прямой с известным элементом подряд, в количестве более 3х.

OxiD ★★★★
() автор топика
Ответ на: комментарий от bugmaker

да. Это нужная инфа. Можно в стек сложить. =) Хотя можешь особо не заморачиваться, я в любом случае смогу обнуление заменить на что-то еще сам )

OxiD ★★★★
() автор топика
Ответ на: комментарий от OxiD

примерно так :

    for (i = 0; i < w; i++) {
        for (j = 0; j < h; j++) {
            // horizontal
            if (i < w1) {
                if (a [i][j] == a [i + 1][j]) {
                    x [j] += 1;
                } else {
                    if (t <= x [j]) {
                        for (k = 0; k <= x [j]; k++) {
                            deleted [i - k][j] = 1;
                        }
                    }
                    x [j] = 0;
                }
            } else {
                if (t <= x [j]) {
                    for (k = 0; k <= x [j]; k++) {
                        deleted [i - k][j] = 1;
                    }
                }
            }
            // vertical
            // forward diagonal
            // backward diagonal
        }
    }

w, h - размер матриц, исходной и для удаления. w1=w-1.
t=минимальное количество одинаковых, подлежащее удалению, без единицы.
х - для кумулятивного накопления строк матрицы Zx...A
Тут толко для горизонтального направления, для остальных аналогично.
Результат - матрица deleted.
В ней в 1 устанавливаются нуждающиеся в удалении.
Сразу обнулять не следует, а только после обработки всей матрицы,
 пройтись по deleted. Иначе можно потерять варианты когда есть 
 ряд одинаковых по нескольким направлениям одновременно.

Возможен другой вариант, когда в дополнительные вектора
 заносятся данные по разным направлениям и сравниваются
 с последующими. Тогда можно обнулять сразу, но оперативы
 потребуется поболее, для хранения этих векторов.

bugmaker ★★★★☆
()
Ответ на: комментарий от bugmaker

вектора х, и потребующиеся для остальных направлений y, b, f, а также матрицу deleted конешно нужно обнулить сперва.

bugmaker ★★★★☆
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.