UVa : 10074 (Take the Land)


Title : Take the Land

Link : http://uva.onlinejudge.org/external/100/10074.html

Tricky Lines :

  1. Your program should take a matrix of 1s and 0s as input and output the area of the largest rectangular piece of land that contain no tree 
  2. Be careful about the efficiency of your program.

Analysis :

  1. firstly, I converted the 0’s to 1’s …. and 1’s to 0’s
    the input array then look like,
    1 0 0 1 0 0 1
    1 1 1 1 1 0 1
    0 1 1 1 1 1 0
    1 0 1 1 1 1 0
    0 0 1 1 1 0 1
    0 0 1 0 0 1 1
  2. Now calculate the accumulated sum of row by row
    that is, New 1
    st row = Old 1st row
    New 2
    nd row = New 1st row + Old 2nd row
    New 3
    rd row = New 2nd row + Old 3rd row
    New 4
    th row = New 3rd row + Old 4th row and so on
    after this operation the array will look like,
    1 0 0 1 0 0 1
    2 1 1 2 1 0 2
    0 2 2 3 2 1 0
    1 0 3 4 3 2 0
    0 0
    4 5 4 0 1
    0 0 5 0 0 1 2
  3. now go through every number and take its consecutive numbers in the same row, which are greater than or equals to that number
    for example, look at the bold part at row 5
    when u r at 4, that means u can take a rectangle of size 4
    at right, u will find a 5, that is greater than or equals to 4
    so, u should take it
    now your rectangle size is 4 + 4 = 8
    not 4 + 5 = 9 // think, why it’s not 9
    then u will find another 4
    now your rectangle size is 4 + 4 + 4 = 12

Runtime : 0.020s

Critical Input : 
4 8
0 0 1 1 1 1 1 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
4 8
0 0 1 1 1 1 0 0
0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0

Critical Output : 
16
16

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

int matrix [100 + 5] [100 + 5];

int main ()
{
    int m, n;

    while ( scanf ("%d %d", &m, &n) ) {
        if ( m == 0 && n == 0 ) break;

        int input;

        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                scanf ("%d", &input);
                matrix [i] [j] = 1 - input;
            }
        }

        for ( int i = 1; i < m; i++ ) {
            for ( int j = 0; j < n; j++ )
                if ( matrix [i] [j] == 1 ) matrix [i] [j] = matrix [i - 1] [j] + 1;
        }

        int maxi = -1;
        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                int cnt = matrix [i] [j];
                for ( int k = j + 1; k < n && matrix [i] [j] <= matrix[i] [k]; k++ )
                    cnt += matrix [i] [j];
                for ( int k = j - 1; k >= 0 && matrix [i] [j] <= matrix [i] [k]; k-- )
                    cnt += matrix [i] [j];
                if ( cnt > maxi) maxi = cnt;
            }
        }

        printf ("%d\n", maxi);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

Another Solution :

Runtime : 0.048s

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

int matrix [100 + 5] [100 + 5];
int save [5050 + 10] [100 + 5];

int main ()
{
    int m, n;

    while ( scanf ("%d %d", &m, &n) ) {
        if ( m == 0 && n == 0 ) break;

        int input;

        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                scanf ("%d", &input);
                matrix [i] [j] = 1 - input;
            }
        }

        int index = 0;

        for ( int k = 0; k < m; k++ ) {
            for ( int i = 0; i < n; i++ ) save [index] [i] = matrix [k] [i];
            index++;

            for ( int i = k + 1; i < m; i++ ) {
                for ( int j = 0; j < n; j++ ) {
                    if ( matrix [i] [j] == 0 ) save [index] [j] = 0;
                    else save [index] [j] = save [index - 1] [j] + 1;
                }
                index++;
            }
        }

        int maxi = -1;
        for ( int i = 0; i < index; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                int cnt = save [i] [j];
                for ( int k = j + 1; k < n && save [i] [j] <= save [i] [k]; k++ )
                    cnt += save [i] [j];
                if ( cnt > maxi) maxi = cnt;
            }
        }

        printf ("%d\n", maxi);
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s