Need help with searching algorithm

[Muffin123]

I have to write this in c, but any thoughts on this would help

 

My problem is i have to read a matrix (which i have coded sucessfully) and then i have to search how many confined areas there are, by that i mean how many areas of 0 are confined by either the boarders of the matrix or the groups of 1s, so in this case the answer would be 4

 

Here is my matrix:

000000000010000000000000000

000000000010000000000000000

000000000010000000000000000

000000000010000000000000000

000000000010000000000000000

000001111111111100000000000

000001000010000100000000000

000001000010000100000000000

000001000010000100000000000

000001000010000100000000000

111111111110000100000000000

000001000000000100000000000

000001000000000100000000000

000001000000000100000000000

000001000000000100000000000

000001111111111111111100000

000000000000000000000000000

000000000000000000000000000

000000000000000000000000000

000000000000000000000000000

000001111111111111111111111

000000000000000000000000000

000000000000000000000000000

000000000000000000000000000

000000000000000000000000000

000000000000000000000000000

000000000000000000000000000

 

Any ideas on how to solve this? ive tried with different kinds of conditions within if statements with no sucess so far (i think this might be similar to the flood fill algorithm but i have no idea how to implement that to fill more than 1 area, if anybody knows how to do that, what i mean by that is to just fill each area with numbers from 1 to n instead of colors, so each confined area has its own number, and i can find the maximum of the table)

[blackadder]

this is one hell of a matrix. thinking of what shapes this encodes blows my mind. 

edit: best of luck man, thank the gods we don't have to do this by hand.

[Muffin123]

this is one hell of a matrix. thinking of what shapes this encodes blows my mind. 

edit: best of luck man, thank the gods we don't have to do this by hand.

This is the really hard one, most of them incorporate only squares and and rectangles, so if you have any ideas for that shoot

[blackadder]

This is the really hard one, most of them incorporate only squares and and rectangles, so if you have any ideas for that shoot

my forte is physics, this is the part i come to one of you guys and ask for help. i have never had to deal with one this crazy, i'm sure i will sometime. i would like to learn how you guys are going to solve this too.  

[mansoor_]

A rough solution paths:

 

(1)have two sets of loops, together they should go through every cell of the matrix (A_i,j, one loop going through all i's (rows) and one for the j's (cols.))

    (2) once you find a cell with a one, you follow the path of ones and if it is a closed loop(confined), as in you end up in the same place you started: then you have one confined area (In your question you did not state whether the edges of the matrix can be included as the boundary of your confined areas)

            (3) now you need to stop the loop (1) from considering all the cells inside (but not including the ones ones on the edge) your confined area, to achieve this you will have to partition the confined area into squares and find the min and max co-ordinates of the squares (the corners)

 

It is quite interesting. I can't code in C but if I could i would have given it a try. 

[Muffin123]

A rough solution paths:

 

(1)have two sets of loops, together they should go through every cell of the matrix (A_i,j, one loop going through all i's (rows) and one for the j's (cols.))

    (2) once you find a cell with a one, you follow the path of ones and if it is a closed loop(confined), as in you end up in the same place you started: then you have one confined area (In your question you did not state whether the edges of the matrix can be included as the boundary of your confined areas)

            (3) now you need to stop the loop (1) from considering all the cells in your confined area, to achieve this you will have to partition the confined area into squares and find the min and max co-ordinates of the squares (the corners)

 

This is not a trivial problem, it is quite interesting. I can't code in C but if I could i would have given it a try. 

If you can do it in java or something similiar it would be of great help, i am quite new to coding myself, i understand what you mean here, but i have no idea how i would go about writing it

[madknight3]

This would be what I would try but I expect there's a more efficient way.

Step 1:    Set a starting id to some unique value.    Set a counter.Step 2:    Find the first available 0.    If no zero is found, then you are done.    Else set it to the starting id and increment the counter.Step 3:    Walk through that section of the maze, setting all touching zeros to the starting id.Step 4:    Change the starting id to another unique value.Step 5:    Repeat steps 2 - 4.The solution will be the number of changes in the starting id (ie: the counter).

[Muffin123]

 

This would be what I would try but I expect there's a more efficient way.

Step 1:    Set a starting id to some unique value.    Set a counter.Step 2:    Find the first available 0.    If no zero is found, then you are done.    Else set it to the starting id and increment the counter.Step 3:    Walk through that section of the maze, setting all touching zeros to the starting id.Step 4:    Change the starting id to another unique value.Step 5:    Repeat steps 2 - 4.The solution will be the number of changes in the starting id (ie: the counter).

I was thinking about that yes, but i have problems with walking trough the one section, i cant seem to write that properly, could you elaborate on how to do that?

[mansoor_]

If you can do it in java or something similiar it would be of great help, i am quite new to coding myself, i understand what you mean here, but i have no idea how i would go about writing it

The approximate psuedo-algorithm for each of the steps:

(1) trivial step....

(2) - inside the inner loop of (1), you have an if statement check whether the cell has a 1

     - If the cell has a one, you check all the cells around that one (by adding one or taking away one from the array counter)

     - start with the cells below it and work clockwise for it to work i.e that cell with the one has cell location (i,j) check (i+1,j) , (i,j+1) , (if diagonals count then include these too), no need to check the cells above that specific array element.

     - every time you move into a new cell with a one in it you take note of it location in another variable, after each step you, you can check whether two the elements(location positions) in this new variables are the same, if they are you have a closed loop

(3)  This one I will leave for you because there are many example of this sort of thing online. 

 

 

(A few added complications

1) If you have a confined area within a confined area, then you need to iterate your main code inside the domain of each of the confined area to check whether they have confined areas within them

2) if the first 1 you find is at a boundary, then you do not necessarily need a closed loop, finding another one at a boundary is sufficient, this can just be another condition you save in a variable you use as the condition for your while loop)

 

I am sorry but i do not have the time to create this code, it would be quite long.  

[madknight3]

I was thinking about that yes, but i have problems with walking trough the one section, i cant seem to write that properly, could you elaborate on how to do that?

 

Hopefully you've already learned about recursion and could write your own recursive algorithm for this.

[SSL]

Possible solution:

Choose an arbitrary replacement "color" (value) and compare it to each element of the array. If it doesn't match, increment the zone counter by one and apply a flood fill of the replacement color, starting from that element. Move to the next element. Repeat until every element of the array has been visited.

 

Implementing flood fill should be straightforward, think recursively and you should be able to come up with a workable method on your own. Of course you can get plenty of implementations online if you want.

[Muffin123]

Possible solution:

Choose an arbitrary replacement "color" (value) and compare it to each element of the array. If it doesn't match, increment the zone counter by one and apply a flood fill of the replacement color, starting from that element. Move to the next element. Repeat until every element of the array has been visited.

 

Implementing flood fill should be straightforward, think recursively and you should be able to come up with a workable method on your own. Of course you can get plenty of implementations online if you want.

Yeah i was thinking about that, however i still dont understand this, say i 'colored' a segment by increasing every number to 2, how would i then go to the next segment and increase that to 3, so i can then find the maximum of the whole array. I was thinking this way, if i add an if in the recursive function, where if everything is colored it should return an integer, and i would then increase the number by 1? 

[WanderingFool]

Yeah i was thinking about that, however i still dont understand this, say i 'colored' a segment by increasing every number to 2, how would i then go to the next segment and increase that to 3, so i can then find the maximum of the whole array. I was thinking this way, if i add an if in the recursive function, where if everything is colored it should return an integer, and i would then increase the number by 1? 

 

Well as SSL said, flood fill is probably the easiest (assuming you use recursion, personally I dislike using recursion on this type of problem because if you get 1000x1000 with all 0's you actually will end up with a stack overflow...but that is beside the point, since you are learning use recursion...and if you come up with a solution and have free time try implementing flood fill without recursion (using stacks)).

 

To address the "color", "color" is just meant as a way to distinguish that you have already processing a point.  So if you know the values inputted are always 0 and 1, then you can use the value 2 to tell your program that you have already processed a pixel (and don't have to enter the recursion loop for it).  Hope that makes sense.

 

e.g.

_abca111b101c101Starting from the (b,b) pixel111121101111121121You would be at (c,c) and looking for the next "0" if we didn't color (b,b) with 2 you would end up going back to (b,b) and end up in an infinite loop.  The purpose of coloring is basically to say that you already processed the pixel

[Muffin123]

I have managed to code something which then produced this

222222222012222222222222222

222222222012222222222222222

222222222212222222222222222

222222222212222222222222222

222222222212222222222222222

222221111111111122222222222

222221333314444122222222222

222221333314444122222222222

222221333314444122222222222

222221333314444122222222222

111111111114444122222222222

222251444444444122222222222

222251444444444122222222222

222251444444444122222222222

222251444444444122222222222

222221111111111111111122222

222222222222222222222222222

222222222222222222222222222

222222222222222222222222222

222222222222222222222222222

222221111111111111111111111

222222222222222222222222222

222222222222222222222222222

222222222222222222222222222

222222222222222222222222222

222222222222222222222222222

222222222222222222222222222

 

So when it returns 7 it should increment the 'color' by 1, but i have a problem that i cant seem to get around, when am i supposed to change the 'color', what are the standards that tell me i have to move to a new cell

int flood(int i, int j, int trenutna, int zamenjat,int visina,int sirina, int tabela[visina][sirina]) {    if ((tabela[i][j]==1) || (tabela[i][j]==0)) {        if (tabela[i][j]==1) {            return 0;        }        tabela[i][j]=zamenjat;        if (tabela[i][j+1]==1) {            flood(i+1,j,trenutna,zamenjat,visina,sirina,tabela);            return 7;        }            if (tabela[i][j]==zamenjat) {            if (tabela[i][j+1]==0) {                //flood(i,j+1,trenutna,zamenjat,visina,sirina,tabela);            }            if (tabela[i][j-1]==0) {               flood(i,j-1,trenutna,zamenjat,visina,sirina,tabela);                           }             if (tabela[i+1][j]==0) {               flood(i+1,j,trenutna,zamenjat,visina,sirina,tabela);                           }            if (tabela[i-1][j]==0) {               flood(i-1,j,trenutna,zamenjat,visina,sirina,tabela);                           }        }                    return 0;    }     return 0;}

[SSL]

Yeah i was thinking about that, however i still dont understand this, say i 'colored' a segment by increasing every number to 2, how would i then go to the next segment and increase that to 3, so i can then find the maximum of the whole array. I was thinking this way, if i add an if in the recursive function, where if everything is colored it should return an integer, and i would then increase the number by 1? 

 

That's the thing, you don't need to change the replacement color. You can use the same color for the WHOLE array. What you do is check if the replacement color matches the target color BEFORE applying the flood fill. Every time you flood fill, increment a zone counter by one. But you are iterating and applying this check to every element in the array.

 

Note that the algorithm you are using here is not flood, it is just using flood under certain conditions. The main loop should be just a simple iteration over all elements; your flood can probably be pretty close to a standard implementation.

[Muffin123]

That's the think, you don't need to change the replacement color. You can use the same color for the WHOLE array. What you do is check if the replacement color matches the target color BEFORE applying the flood fill. Every time you flood fill, increment a zone counter by one. But you are iterating and applying this check to every element in the array.

 

Note that the algorithm you are using here is not flood, it is just using flood under certain conditions. The main loop should be just a simple iteration over all elements; your flood can probably be pretty close to a standard implementation.

Im trying to do this on my own cuz i have no idea how to implement flood properly, so if im getting this right, youre saying i increase the first cell to say 2, then i increase every cell around it confined by 1s untill i cant anymore, then find the next 0 and put that up to say 3 then repeat?

[SSL]

Im trying to do this on my own cuz i have no idea how to implement flood properly, so if im getting this right, youre saying i increase the first cell to say 2, then i increase every cell around it confined by 1s untill i cant anymore, then find the next 0 and put that up to say 3 then repeat?

 

No.

 

Target color: "0" (empty elements)

Border color: "1"

Replacement color: "2"

• For each element in the array, compare the color to the target color.
• If the colors are equal, flood fill with the replacement color starting at the current pixel, and increment the zone counter by one.
• Continue iteration.

Imagine an array filled with all zeros (no borders). Start iteration; compare "0" to the color of the current element. The element's color is "0", so they are equal. Perform a flood fill starting on this element and increment the zone counter by 1. Next element; compare "0" to the color of the current element. The element's color is "2" so we do nothing and continue the loop. Since the array has only one region, every element was colored by the first flood fill operation and the loop iteration will finish without doing anything else. The zone counter will remain at 1.

[Muffin123]

No.

 

Target color: "0" (empty elements)

Border color: "1"

Replacement color: "2"

• For each element in the array, compare the color to the target color.
• If the colors are equal, flood fill with the replacement color starting at the current pixel, and increment the zone counter by one.
• Continue iteration.

Imagine an array filled with all zeros (no borders). Start iteration; compare "0" to the color of the current element. The element's color is "0", so they are equal. Perform a flood fill starting on this element and increment the zone counter by 1. Next element; compare "0" to the color of the current element. The element's color is "2" so we do nothing and continue the loop. Since the array has only one region, every element was colored by the first flood fill operation and the loop iteration will finish without doing anything else. The zone counter will remain at 1.

Yeah, but what i dont understand is, how do i know that that zone is filled, i tried what youre saying already and it will basically just color anything it sees without ever incrementing the counter. this is basically what you mean right? (minus the return 7 if part, apparently there is never an occurance that the next element is a 1 when there clearly is several cases???)

if (tabela[i][j]==zamenjat) return 0;    if (tabela[i][j]==trenutni) {        tabela[i][j]=zamenjat;        if (tabela[i][j+1]==1) {            return 7;        } else {            flood(i+1,j,trenutni,zamenjat,visina,sirina,tabela);            flood(i-1,j,trenutni,zamenjat,visina,sirina,tabela);            flood(i,j+1,trenutni,zamenjat,visina,sirina,tabela);            flood(i,j-1,trenutni,zamenjat,visina,sirina,tabela);                    }    }    return 0;

  

[SSL]

Yeah, but what i dont understand is, how do i know that that zone is filled, i tried what youre saying already and it will basically just color anything it sees without ever incrementing the counter. this is basically what you mean right? (minus the return 7 if part, apparently there is never an occurance that the next element is a 1 when there clearly is several cases???)

 

You know a zone is filled if it is not equal to the target color. In this case, your target color is "0" because that is the initial value of the array elements.

[Muffin123]

You know a zone is filled if it is not equal to the target color. In this case, your target color is "0" because that is the initial value of the array elements.

Yeah but then it will just keep looping and finding new zones to fill, without increasing the counter

[SSL]

Yeah but then it will just keep looping and finding new zones to fill, without increasing the counter

 

You iterate over the entire array once, after reaching the end of the array you stop. At that point there can be no more zones to fill.

[Muffin123]

You iterate over the entire array once, after reaching the end of the array you stop. At that point there can be no more zones to fill.

Im not sure we are on the same page here, this is the matrix i have: 

000000000010000000000000000000000000010000000000000000000000000010000000000000000000000000010000000000000000000000000010000000000000000000001111111111100000000000000001000010000100000000000000001000010000100000000000000001000010000100000000000000001000010000100000000000111111111110000100000000000000001000000000100000000000000001000000000100000000000000001000000000100000000000000001000000000100000000000000001111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

As you can see it has 4 areas, when i iterate over it, the thing doesnt care if a 0 is outside of my area, it will just replace it, what i end up with is the same matrix just replaced by 2s instead of 0s

[Muffin123]

Im not sure we are on the same page here, this is the matrix i have: 

000000000010000000000000000000000000010000000000000000000000000010000000000000000000000000010000000000000000000000000010000000000000000000001111111111100000000000000001000010000100000000000000001000010000100000000000000001000010000100000000000000001000010000100000000000111111111110000100000000000000001000000000100000000000000001000000000100000000000000001000000000100000000000000001000000000100000000000000001111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

As you can see it has 4 areas, when i iterate over it, the thing doesnt care if a 0 is outside of my current area, it will just replace it, what i end up with is the same matrix just replaced by 2s instead of 0s

[SSL]

Im not sure we are on the same page here, this is the matrix i have: 

 

As you can see it has 4 areas, when i iterate over it, the thing doesnt care if a 0 is outside of my area, it will just replace it, what i end up with is the same matrix just replaced by 2s instead of 0s

 

Yes, but you are keeping track of each time that happens. Because a flood fill will color EVERY contiguous element, you know that when you next encounter an uncolored element you have also reached a new region. Without the fill, you have no way of knowing if a "0" element is part of the same region or not.

[Muffin123]

Yes, but you are keeping track of each time that happens. Because a flood fill will color EVERY contiguous element, you know that when you next encounter an uncolored element you have also reached a new region. Without the fill, you have no way of knowing if a "0" element is part of the same region or not.

The problem is then that my function is faulty, it recognises some parts as a new part, but others just get painted over with another color