|
|
|
поиск множеств содержащих одинаковые элементы.
|
|||
|---|---|---|---|
|
#18+
Добрый день! Что-то не могу придумать достаточно эффективный алгоритм для нахождения множеств содержащих одинаковые числа, ну например на матрице Код: plaintext 1. 2. 3. хочу получить множества: [fix] 2 4 4 4 4 2 2 2 2 2 66 [/fix] в виде списка их координат: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. пытался придумать что-то типа dfs: ( псевдокод ) [src] void dfs(int i, int j, list L) { visited[i][j] = true; list.add( i, j ); if ( i + 1 < height && !visited[i][j] && matrix[i][j] == matrix[i+1][j]) { dfs( i + 1, j ); } // аналогично с // ( i - 1, j ), // ( i, j - 1 ), // ( i, j + 1 ) } [src] но мне кажется есть более эффективный способ! Какие идеи ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.05.2011, 14:57 |
|
||
|
поиск множеств содержащих одинаковые элементы.
|
|||
|---|---|---|---|
|
#18+
scymaks, Можно переформулировать задание? Скажем, на входе - матрица MxN целых чисел, из которых некоторые повторяются. Что должно быть на выходе? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.05.2011, 15:11 |
|
||
|
поиск множеств содержащих одинаковые элементы.
|
|||
|---|---|---|---|
|
#18+
На выходе нужно получить список множеств, где каждое множество состоит из пар вида (x,y) где x и y это индексы элемента ну то есть например на матрице [fix] 2 1 2 1 1 2 [/fix] нужно получить на выходе Код: plaintext 1. 2. 3. Вот... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.05.2011, 15:52 |
|
||
|
поиск множеств содержащих одинаковые элементы.
|
|||
|---|---|---|---|
|
#18+
scymaks, Что значит - "ещё одно множество, содержащее 2"? Почему бы тогда тупо не выделить каждый элемент в индивидуальное множество и вывести M*N множеств по одному элементу? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.05.2011, 17:27 |
|
||
|
поиск множеств содержащих одинаковые элементы.
|
|||
|---|---|---|---|
|
#18+
не понял, объяснитесь ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.05.2011, 17:36 |
|
||
|
поиск множеств содержащих одинаковые элементы.
|
|||
|---|---|---|---|
|
#18+
scymaksНа выходе нужно получить список множеств, где каждое множество состоит из пар вида (x,y) где x и y это индексы элемента ну то есть например на матрице Код: plaintext 1. нужно получить на выходе Код: plaintext 1. 2. 3. Вот... Чем плох выход M1={ (0,0) }, M2={ (0,1) }, M3={ (0,2) }, M4={ (1,0) }, M5={ (1,1) }, M6={ (1,2) } ? Если же Вам нужно выделить связные области, заполненные одинаковыми числами, то почему в первом примере во втором множестве нет (1,2)? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.05.2011, 18:03 |
|
||
|
поиск множеств содержащих одинаковые элементы.
|
|||
|---|---|---|---|
|
#18+
=) потому что опечатался ) и да, нужно найти связные области :) вы знаете как это сделать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.05.2011, 19:03 |
|
||
|
поиск множеств содержащих одинаковые элементы.
|
|||
|---|---|---|---|
|
#18+
scymaks, Известный мне алгоритм (названия не помню) использует матрицу-спутника: заводится дублирующая матрица того же размера, после чего примерно так: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.05.2011, 21:21 |
|
||
|
|

start [/forum/topic.php?fid=16&tid=1342947]: |
0ms |
get settings: |
8ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
174ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
45ms |
get tp. blocked users: |
1ms |
| others: | 232ms |
| total: | 492ms |

| 0 / 0 |
