Recursive problems in 2D array C++

Question

I have a problem that from a certain number 1 in a 2D matrix with (x, y) coordinates. From this number, it will start spreading out its 4-neighbor which their values will be assigned by (start point + 1)

We start from a coordinate of (3, 3) = 1. Its neighbor's value will be 2. Next step, 4 neighbors of the point having value of 2 will be 3. And so on, until, all 1 numbers in the matrix are infected!

I have resolved this problem by using some loops. However, I'd like to resolve it by another way that is recursion. But I haven't done with it.

Before

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

After spreading out

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

Below is my code but I just can spread all 1 numbers with another value but not as I want. So please help me resolve this problem.

#include <iostream>
#define MAX 10

using namespace std;

int data[MAX][MAX] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 1, 1, 1, 0, 0, 0, 0, 0},
    {0, 0, 1, 1, 1, 1, 1, 1, 0, 0},
    {0, 0, 1, 1, 1, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
    {0, 0, 1, 1, 1, 0, 0, 0, 0, 0},
    {0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
};

int mark[MAX][MAX];


void spreading(int x, int y, int v){
    if (x < 0 || x == MAX) return;
    if (y < 0 || y == MAX) return;

    if(data[x][y] == 0 || mark[x][y] != 0)
        return;
    data[x][y] = v;
    mark[x][y] = v;

    spreading(x + 1, y, v);
    spreading(x, y + 1, v);
    spreading(x - 1, y, v);
    spreading(x, y - 1, v);
}

void printArr(int a[MAX][MAX]){

    for (int i = 0; i < MAX; ++i) {
        cout << endl;
        for (int j = 0; j < MAX; ++j) {
            cout << a[i][j] << " ";
        }
    }
}

int main(){

    spreading(3, 3, 1);
    printArr(data);
    system("pause");
    return 0;
}

Why do you want a recursive solution? This one is probably better. — Beta
– Beta, Commented Feb 24, 2014 at 14:00
Yes. This is my coursework and I have recently learned about Recursion. So I want to resolve it with recursive solution. It's just I want to improve my programming skill with recursion. — Long Uni
– Long Uni, Commented Feb 24, 2014 at 14:07
2 points: 1) v is always 1 and you are assigning (not adding) v in the array, so you can never have more than 1 in the array (unlike your original result) if v is constant, do you need it as parameter? ; 2) I'm not sure if order is essential, but you are first always incrementing x until finished before incrementing/decremeting y. Is this as expected? — stefaanv
– stefaanv, Commented Feb 24, 2014 at 14:20
Looking again at the original result, I would suspect that the order of incrementing (my point 2) is okay, so passing v+1 to spreading() should be okay, as answered by Jarod42 — stefaanv
– stefaanv, Commented Feb 24, 2014 at 14:25

Jarod42 · Accepted Answer · 2014-02-24 15:03:15Z

2

Following may solve your issue: (https://ideone.com/VQmBhU)

void spreading(int x, int y, int v){
    // Test if x, y is inside the propagation area
    if (x < 0 || x == MAX) return;
    if (y < 0 || y == MAX) return;
    if (data[x][y] == 0) return;

    // if already visited with a better path, cancel.
    // if not visited, or the previous visit was worst than this try, continue
    if (mark[x][y] != 0 && mark[x][y] <= v) return;

    data[x][y] = v;
    mark[x][y] = v;

    spreading(x + 1, y, v + 1);
    spreading(x, y + 1, v + 1);
    spreading(x - 1, y, v + 1);
    spreading(x, y - 1, v + 1);
}

Some example of 're' visit (with the mark array content):

(1) 0  ->   1 (2)   -> 1  2  ->  1  2
 0  0       0  0       0 (3)    (4) 3

1 <= 5, 3 <= 5 : (4) finished
2 <= 4 : (3) finished
1 <= 3 : (2) finished
4 > 2 : we continue propagation from (1)

(1) 2  ->   1  2
 4  3      (2) 3

...

edited Feb 24, 2014 at 15:03

answered Feb 24, 2014 at 14:24

Jarod42

227k15 gold badges214 silver badges350 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Long Uni Over a year ago

I appreciate your solution but can you tell me more detail about a condition: if (mark[x][y] != 0 && mark[x][y] <= v) return;

Jarod42 Over a year ago

As we do a Depth-first_search, some visited case will have higher value than expected. when we visit these node later, we really want to update these node if we have a shorter path, but if our path is longer, we don't want to propagate any more.

Collectives™ on Stack Overflow

Recursive problems in 2D array C++

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related