TCO11 Qual3 Hard(1000) ComplementMachine2D

ComplementMachine2D

00  01
01  11

このようになっていたら、この４マス全部が消去可能な部分マトリックスに含まれることはない。各部分マトリックスについて、このような４マスを含まないかどうか調べる。

#include <string>
#include <vector>
using namespace std;

class ComplementMachine2D{public:
int largestSubmatrix( vector <string> matrix )
{
    int N = (int)matrix.size();
    int M = (int)matrix[0].size();

    vector<vector<bool> > F( N, vector<bool>(M) );

    for ( int y=0; y<N-1; y++ )
    for ( int x=0; x<M-1; x++ )
    {
        int c = (matrix[y  ][x  ]-'0') +
                (matrix[y+1][x  ]-'0') +
                (matrix[y  ][x+1]-'0') +
                (matrix[y+1][x+1]-'0');
        F[y][x] = c!=1 && c!=3;
    }

    int ans = 0;

    for ( int y1=0;  y1<N; y1++ )
    for ( int y2=y1; y2<N; y2++ )
    for ( int x1=0;  x1<M; x1++ )
    for ( int x2=x1; x2<M; x2++ )
    {
        bool f = true;
        for ( int y=y1; y<y2 && f; y++ )
        for ( int x=x1; x<x2 && f; x++ )
            if ( ! F[y][x] )
                f = false;

        if ( f )
            ans = max( ans, (y2-y1+1)*(x2-x1+1) );
    }

    return ans;
}};