SRM525 Div1 Easy(300), Div2 Medium(600) DropCoins

TopCoder

DropCoins

残るのは矩形の中にあるコイン。全ての矩形についてコインがK枚かどうかを調べる。

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

class DropCoins{public:
int getMinimum( vector <string> board, int K )
{
    int H = (int)board.size();
    int W = (int)board[0].size();

    int ans = -1;

    for ( int y1=0; y1<H; y1++ )
    for ( int x1=0; x1<W; x1++ )
    for ( int y2=y1+1; y2<=H; y2++ )
    for ( int x2=x1+1; x2<=W; x2++ )
    {
        int k = 0;
        for ( int y=y1; y<y2; y++ )
        for ( int x=x1; x<x2; x++ )
            if ( board[y][x]=='o' )
                k++;
        int s = 2*min(y1,H-y2)+max(y1,H-y2)
              + 2*min(x1,W-x2)+max(x1,W-x2);
        if ( k==K &&
            ( ans==-1 || ans>s ) )
            ans = s;
    }

    return ans;
}};