Обход квадратной матрицы, объединяющий соседние ячейки с одинаковыми значениями - PullRequest
Новая
       16

Обход квадратной матрицы, объединяющий соседние ячейки с одинаковыми значениями

0 голосов
/ 28 июня 2018

Учитывая образец квадратной матрицы (0,1), как показано ниже: 

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

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

Group #1: (0,1), (0,2), (1,2), (2,3)
Group #2: (1,5), (2,5), (3,5), (4,5)
Group #3: (3,0), (4,1), (5,0)
Group #4: (5,3)

Мой текущий алгоритм выглядит следующим образом: 

for i = 0, i < matrix.dimension, i++
   for j = 0, j < matrix.dimension, j++
       if (i,j),(i,j+1),(i,j-1),(i-1,j),(i-1,j+1),(i-1,j-1),(i+1,j),(i+1,j+1),(i+1,j-1) = 1 
           push all pairs of i, j = 1 into a group

Но тогда я застрял в том, как разделить (2,3) и (2,5) на 2 группы, поскольку они все еще находятся в диапазоне (i+/-1, j+/-1), если я, например, перейду к ячейке (2,4). Ваша помощь приветствуется. Заранее спасибо.

1 Ответ

0 голосов
/ 28 июня 2018

Вы можете визуализировать эту матрицу в виде графика. Таким образом, в каждой координате (x,y) эта точка связана с 8 другими точками, т.е.

(x+1, y) (x+1,y-1) (x+1,y+1) (x,y+1) (x,y-1) (x-1,y) (x-1,y+1) (x-1,y-1).

Таким образом, ваша точка (x,y) будет связана с вышеуказанными 8 точками. Теперь у вас есть готовый график перед вами.

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

Надеюсь, это поможет!

...