Dynamic programming: Find largest diamond (rhombus)

Question

I have a small program to do in Java. I have a 2D array filled with 0 and 1, and I must find the largest rhombus (as in square rotated by 45 degrees) and their numbers.

Example:

0 1 0 0 0 1

1 0 1 1 1 0

1 0 1 1 1 1

0 1 1 1 1 1

0 0 1 1 1 1

1 1 1 1 1 1

Result:

      1    

    1 1 1  

  1 1 1 1 1

    1 1 1  

      1    

The problem is similar to this SO question.

If you have any idea, post it here.

Answer 1

Short tutorial:

How would you solve the problem if it was a 1x1-field?
How could you formulate the problem recursively?
How could you remember intermediate results and use them?
Do it.

Answer 2

This too long for a comment. I'll post my solution later on if you can't solve it but here's how I've done it (in less than 15 lines of code): I first created a second array (a little big bigger [n+2][n+2]) and did n/2 pass:

0 0 0 0 0 0 0 0 
0 0 1 0 0 0 1 0 
0 1 0 1 1 1 0 0 
0 1 0 1 2 2 1 0 
0 0 1 2 2 2 1 0 
0 0 0 1 2 2 1 0 
0 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 
0 0 1 0 0 0 1 0 
0 1 0 1 1 1 0 0 
0 1 0 1 2 2 1 0 
0 0 1 2 3 2 1 0 
0 0 0 1 2 2 1 0 
0 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0

Where a non-zero number x means "I'm the center of a rhombus of size x" (I'm expressing the size in relation with the length of the diagonals [which are both equal in your case] of the rhombus). You can find if you have the center of a rhombus of size (k+1) by checking if {top,right,down,left} are all the centers of rhombus of size k.

The advantage of first creating a bigger array is that it really simplifies your logic but I could do it in place, with a more convoluted logic, by modifying the original array or by using a second array of the same size as the input (once again, it's way easier to simply put a safe "fence" of all-zeroes around your input).

If you don't "surround" your array with a fence, you have a lot of additional if/else checks: this would be prone to errors, lead to bigger code and lead to uglier code.

Answer 3

void rhombus()
{
    maxr=0;
    for (int i=n-1;i>=0;i--)
    {
        for (int j=n-1;j>=0;j--)
        {
            if (b[i][j]>0)
            {
                if ((i==n-1) || (j==n-1) || (i==0) || (j==0)) b[i][j]=1;
                else {
                    b[i][j]=min4(b[i][j+1],b[i][j-1],b[i+1][j],b[i-1][j])+1;
                    if (b[i][j]==maxr) nrr++;
                    else if (b[i][j]>maxr) {
                        nrr=1;
                        maxr=b[i][j];
                    }
                }
            }
        }
    }
}

Did it,it works,this is my function,where maxr is the max size of the rhombus,and nrr is the number of max sized rhombus.Not sure how it works on huge arrays.(i loop this function n/2 times)