SRM494 Div1 Easy(250), Div2 Medium(500) Painting

Painting

O(N⁴)で書いたけど、O(N⁵)でも間に合うらしい。

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

class Painting{public:
int largestBrush( vector <string> picture )
{
    int N = (int)picture.size();
    int M = (int)picture[0].size();

    vector<vector<int> > P(N,vector<int>(M,1));

    for ( int x=0; x<N; x++ )
    for ( int y=0; y<M; y++ )
    if ( picture[x][y]=='B' )
    {
        int S = min(N-x,M-y);
        for ( int xx=0; xx+x<N; xx++ )
        for ( int yy=0; yy+y<M; yy++ )
            if ( picture[xx+x][yy+y] == 'W' )
                S = min(S,max(xx,yy));

        for ( int xx=0; xx<S; xx++ )
        for ( int yy=0; yy<S; yy++ )
            P[xx+x][yy+y] = max( P[xx+x][yy+y], S );
    }

    int ans = N;

    for ( int x=0; x<N; x++ )
    for ( int y=0; y<M; y++ )
    if ( picture[x][y] == 'B' )
        ans = min( ans, P[x][y] );

    return ans;
}};