fork download

copy

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

class VegetableField {
    public: int biggestPlot(vector <string>);
};

template <class T> inline void checkmax( T &a, T b) { if(a<b) a=b; }

int cnt[256];

int VegetableField::biggestPlot(vector <string> field) {
    /*
    In this problem we are asked to find a rectangle, which is
    formed with (at most two) different characters and also have
    the biggest area. As the given plot is relatively small (20x20),
    we can just generate all possible rectangles and choose the
    biggest one.

    This bruteforce solution has time complexity of O(R^3+C^3), where
    R and C are the numbers of rows and columns respectively.
    */
    int i, j, k, l, m, n;
    int R = field.size(), C = field[0].size();
    int answer = 0, diff;
    for(int i=0; i<R; i++) for(int j=0; j<C; j++) {
        /*
        These two loops will get all the top-left possible corners
        of all rectangles.
        */
        for(int k=i; k<R; k++) for(int l=j; l<C; l++) {
            /*
            These two loops will get all the down-right possible
            corners of all rectangles.

            Now the rectangle is (i, j), (k, l), where the first
            pair is top-left corner and the other one -
            the bottom-right.
            */
            diff=0;
            memset(cnt, 0, sizeof(cnt));
            for(m=i; m<=k; ++m) for(int n=j; n<=l; ++n) {
                /*
                Counting the different number of characters is easy
                through the global array cnt[].
                */
                if(++cnt[(int)field[m][n]]==1) {
                    if(++diff>2) break;
                }
            }
            /*
            The rectangle is proper iff the number of different
            chars is at most 2. If so update if it is bigger than
            the last one.
            */
            if(diff<=2) {
                checkmax(answer, (k-i+1)*(l-j+1));
            }
        }
    }
    return answer;
}

prog.cpp: In member function ‘int VegetableField::biggestPlot(std::vector<std::basic_string<char> >)’:
prog.cpp:25:9: warning: unused variable ‘i’ [-Wunused-variable]
     int i, j, k, l, m, n;
         ^
prog.cpp:25:12: warning: unused variable ‘j’ [-Wunused-variable]
     int i, j, k, l, m, n;
            ^
prog.cpp:25:15: warning: unused variable ‘k’ [-Wunused-variable]
     int i, j, k, l, m, n;
               ^
prog.cpp:25:18: warning: unused variable ‘l’ [-Wunused-variable]
     int i, j, k, l, m, n;
                  ^
prog.cpp:25:24: warning: unused variable ‘n’ [-Wunused-variable]
     int i, j, k, l, m, n;
                        ^
/usr/lib/gcc/i486-linux-gnu/4.8/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status

Standard output is empty