Welcome to The Rice Fields!

Solution:

Representing a square in the matrix - for my solution, I used special way to describe square's position and side length, nothing too flashy, but quite useful. I will explain it on the example provided with the problem.

On the left is what we get from the start, on the right is the final product

In the left picture, each number describes whether the current field is usable (plant) or unusable (water). In the right picture, each field is actually the lower-right point of square and the number in that field is square's side length. If the number in a field is zero, then no square fits in there, while for non-zero number it is the opposite.

Now, with such way of presenting a square, certain rules are created.

1. A number in matrix $N_{x, y}$ is always equal to $0$ if the current field (x,y) is water.

2. A number in matrix $N_{x, y} = 1 + min(N_{x-1, y} \space ,\space N_{x-1, y-1} \space ,\space N_{x, y-1} )$ if the current field is plant.

3. A number outside of the matrix is also always a null (such numbers are used in formula from rule 2 few times).

If these 3 rules are transformed in few if statements, "the final product" is acquired, where the biggest number in whole matrix is the side length of the biggest square. In $1000\times1000$ matrix that is described in the .txt file, the biggest square has side length $16$ , meaning its area is $\boxed{256}$ .

In addition to the other solutions, I think this thoroughly explains the process. The program goes to every element of the 1000x1000 matrix. If a 1, it goes down that column of ones and tries to make squares going out to the right from that side created. It loks at the length of the row of 1s coming out and the different square sizes that can support with whatever length of the rows above and below it are.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//go through all elements of the 1000x1000
for(int down = 0 ; down < size ; down++){
for(int across = 0 ; across < size ; across++){
if([[[array objectAtIndex:down] objectAtIndex:across] integerValue]){
    //if a one then move down then across then
    int count = 1 ;
    for(; count + down < size; count++){ //start a column of 1s
    if(![[[array objectAtIndex:down+count] objectAtIndex:across] integerValue]) break ;
    NSMutableArray *hopeful = [NSMutableArray new] ;

    //go upward, starting at the bottom of column of 1s, then across
     for(int b = 0; b < count; b++){
         int c = 0 ;
         for(; c < count && c + across < size ; c ++){
             if(![[[array objectAtIndex:down+count-1-b] objectAtIndex:across+c] integerValue])break ;
             [hopeful addObject:[NSNumber numberWithInt:c]] ;
         } //get number of 1s going across coming out of the column of 1s, add to "hopeful"

         NSInteger hopeCount = hopeful.count ;

         //here based on numbers get the max possible square
         for(int b = 0 ; b < hopeCount- 1 ; b ++){
         for(int d = 0 ; d < [[hopeful objectAtIndex:b] integerValue] -1 ; d ++){  
             //incremenet the starting value to get all smaller cases

             //original is the original length of the row going out of the column, check if it forms a square
             NSInteger original = [[hopeful objectAtIndex:b] integerValue] -d;
             BOOL success = true ;
             if(hopeCount - b < original) success = false ;
             for(int c = b + 1; c < hopeCount && c-b < original && success; c ++){
                 if([[hopeful objectAtIndex:c] integerValue] < original) success = false ; 
              }
             if(success && original > highest) highest = original ;

In Java: open the input file in BufferedReader ipf , then:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

String[] dimensions = ipf.readLine().split(" ");

int N = Integer.parseInt(dimensions[0]);
int M = Integer.parseInt(dimensions[1]);            
int maxS = 0;

String[] values;
int sq[] = new int[M];

for (int x = 0; x < M; x++) sq[x] = 0;

for (int y = 0; y < N; y++) {
    values = ipf.readLine().split(" ");

    int left = 0, topleft = 0;
    for (int x = 0; x < M; x++) {
        int top = sq[x];

        if (Integer.parseInt(values[x]) == 1) {
            sq[x] = Integer.min(top,Integer.min(left,topleft)) + 1;
            if (sq[x] > maxS) maxS = sq[x];
        } else sq[x] = 0;

        topleft = top; left = sq[x];
    }
}

System.out.println(maxS*maxS);

Output:

1

256

Explanation: Array sq[x] is the side of the greatest square whose bottom-right corner lies in the current row at position $x$ .

If a tile contains water, it cannot be part of a square, so sq[x] = 0 in that case.

If a tile contains plants, we look at the neighboring tiles above, left, and top-left. If they all are the bottom-right corner of a square of size $n$ or more, then we have now found a square of size $n+1$ . In other words, we take thee minimum value of sq[...] for these neighbors and add one. The variables top , left , and topleft provide the necessary bookkeeping. They allow us to process the entire situation without storing the entire array.

I imported the .txt file into a MS excel spreadsheet using the excel text import wizard. I then made a few lines of VBA code to search the sheet for the largest square area the contained all 1's. It is not an elegant solution but it gets the job done.

 Function Col_Letter(lngCol As Integer) As String
 Dim vArr
 vArr = Split(Cells(1, lngCol).Address(True, False), "$")
Col_Letter = vArr(0)
End Function


  Private Function chkblk(rw As Integer, cl As Integer, sd As Integer) As Integer
   For trw = 0 To sd
       For tcl = 0 To sd
       If Worksheets("Data").Cells(rw + trw, cl + tcl).Value = 0 Then
          chkblk = (tcl + 1)
          Exit Function
       End If

     Next tcl
     Next trw
     chkblk = 0
      End Function


 Sub areafind()
    Dim col As Integer
    Dim row As Integer
    Dim side As Integer
    col = 1
   row = 1
   side = 2
 While (row <= (1000 - side))
    Worksheets("results").Range("C10").Value = row
    While (col <= (1000 - side))
         Worksheets("results").Range("C11").Value = col
         Worksheets("results").Range("E11").Value = Col_Letter(col)
         While (chkblk(row, col, side) = 0)
         side = side + 1
              Worksheets("results").Range("C4").Value = row
              Worksheets("results").Range("C5").Value = col
              Worksheets("results").Range("E5").Value = Col_Letter(col)
              Worksheets("results").Range("C6").Value = side
        Wend
        col = col + chkblk(row, col, side)
   Wend
   row = row + 1
    col = 1
Wend

End Sub

Lets define an dynamic Dij = sum of '1' from start to (i,j): Dij = D(i-1)j + Di(j-1) - D(i-1)(j-1) + Aij

Then let`s fix point i,j, than we can find the max square with binary search. Sum from (i,j) to (i2,j2) = Di2j2 - D(i-1)j2 - Di2(j-1) + D(i-1)(j-1)

Answer is max answer for all (i,j)

So, final complexity is O(n m log(max(n,m)))