0

As mentioned the title above. I want to find out whether there are how many components in a 2D Array. Whereas, components are made by 1 numbers and there are only 0 and 1 number in the array. I implemented this problem by using DFS (Deep First Search) algorithm with recursive calls and an array to mark cell visited. However, I want to implement this problem with another way without using recursion, stack, queue, struct... Only using for/while function are allowed.

Example: Array data:

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

Array after determined components with specific labels.

0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 2 2 2 0 3 3 0 1 0 0 0 0 0 1
0 0 2 0 2 0 3 3 0 1 0 4 4 4 0 1
0 0 2 0 2 0 0 0 0 1 0 4 0 4 0 1
0 0 2 0 2 0 0 0 0 1 0 4 0 4 0 1
0 0 2 2 2 0 0 0 0 1 0 4 0 4 0 1
0 0 0 0 0 5 5 5 0 1 0 4 4 4 0 1
0 0 0 0 0 5 0 5 0 1 0 0 0 0 0 1
0 0 0 0 0 5 5 5 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 6 6 6 6 6 0 0 0 0 7 7 7 7 0 0
0 6 0 0 0 6 0 0 0 0 7 0 0 7 0 0
0 6 0 6 6 6 6 6 0 0 7 7 7 7 0 0
0 6 0 6 0 6 0 6 0 0 7 7 7 7 0 0
0 6 6 6 6 6 6 6 0 0 0 0 0 0 0 0
0 6 6 6 6 6 6 6 0 0 0 0 0 0 0 0

Thank you in advance.

Ahmad F
  • 30,560
  • 17
  • 97
  • 143
Long Uni
  • 101
  • 3
  • 12
  • It will be better if you share why you would do this, and what you have tried so far. – herohuyongtao Mar 03 '14 at 15:12
  • Related: http://stackoverflow.com/questions/20844517/recursive-function-to-loop-and-stack – herohuyongtao Mar 03 '14 at 15:13
  • Actually, this is my homework and I just stated programing recently. My teacher doesn't allow me to use something that is beyond lesson in my class. That's why I used recursive function in DFS algorithm for this problem but it is not accepted. Using stack, queue, structure are also not allowed. I only can use for/while loop, normal function for this problem. Hope you can sympathize! – Long Uni Mar 03 '14 at 15:17

1 Answers1

0

I guess you could iterate through the matrix, and check the neighbours for each cell, and copy the value of the neighbour if that is > 0 or set a new value if all the neighbours are 0. In pseudocode:

comp = 1
for i = 0 to n:
  for j = 0 to n:
    for nei : neighbours(i, j):
      if nei > 0:
        m[i,j] = nei
        break
      m[i,j] = comp
      comp++

And neighbours are the 4 (or 2) adjacent neighbouring cells to (i, j)

QQQ
  • 41
  • 2
  • 6