Search code examples
c#recursion

Find in how many pieces a matrix was sliced into with recursion

I recently got an assignment, where I a have 4 by 5 matrix with 0 and 1 (zero's represent the cut parts of the matrix). I need to find a way to calculate in how many pieces matrix will be sliced and as I mentioned zero's represent the cut parts of the matrix so if from one border to another goes straight line of zero's it means the matrix was sliced on that line, as for example (in this pic I've marked where matrix would be split, a line of zeros slice it):

enter image description here

So guys I know that you won't entirely solve this code for me and I don't need that, but what I need is to understand this:

  1. Firstly how should I tell a compiler in which direction (when it is going through matrix) it should be going, I have an idea with enumerations?
  2. Secondly, what kind of condition sentence I should use that the compiler would recognize the line of zeros (if there is such)?

Any help would be appreciated

Solution

  • You did not specify any requirements for the algorithm (such as time and space complexity), so I guess one answer, that correlates to some specific solutions, would be:

    1. Go in all 4 directions
    2. Don't condition on 0s to create the line, but try to look at the 1s and find to which piece they belong.

    A general algorithm for this can be implemented as follows:

    1. Create a helper matrix of the same size, a function to give you a new symbol (for example by increasing some number any time a symbol is asked for), and a data structure to store collisions
    2. Go in all 4 directions starting from anywhere
    3. Whenever you find a 0 in the original matrix, issue some new symbol to each of the new directions you are going from there

    4. Whenever you find 1, try to store the values in the helper matrix. If there is already a value there, then:

      1. Store in the collisions data structure that you found a collision between 2 symbols

      2. Don't continue in any direction from this one.

    This will traverse each cell at most 4 time, so time complexity is O(n), and when you are done you will have a data structure with all the collisions. Now all you need to do is combine all entries in the other data structure to collect how many unique pieces you really have.