SRM455 Div1 Easy(300) DonutsOnTheGridEasy

TopCoder

DonutsOnTheGridEasy

動的計画法。num(x1,y1,x2,y2)を(x1,y1)-(x2,y2)の長方形が含むドーナツの個数とすると、

num(x1,y1,x2,y2) = min(
　num(x1+1,y1,x2,y2),
　num(x1,y1+1,x2,y2),
　num(x1,y1,x2-1,y2),
　num(x1,y1,x2,y2-1),
　num(x1+1,y1+1,x2-1,y2-1)+1, （この長方形がドーナツの場合）
)

である。

長方形がドーナツかどうかを逐一判定していると時間をオーバーしてしまうので、長方形の各辺について0が連続しているかどうかをあらかじめ調べておく。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class DonutsOnTheGridEasy
{
public:
    int calc( vector <string> grid );
};

int DonutsOnTheGridEasy::calc( vector <string> grid )
{
    int W = (int)grid.size();
    int H = (int)grid[0].size();

    //  [x1][y1][x2]　(x1,y1)-(x2,y1)は0が連続している
    bool hzero[50][50][50];
    //  [x1][y1][y2]　(x1,y1)-(x1,y2)は0が連続している
    bool vzero[50][50][50];
    
    for ( int x1=0; x1<W; x1++ )
    for ( int y1=0; y1<H; y1++ )
    {
        hzero[x1][y1][x1] = vzero[x1][y1][y1] = grid[x1][y1] == '0';

        for ( int x2=x1+1; x2<W; x2++ )
            hzero[x1][y1][x2] = grid[x2][y1]=='0' && hzero[x1][y1][x2-1];
        for ( int y2=y1+1; y2<H; y2++ )
            vzero[x1][y1][y2] = grid[x1][y2]=='0' && vzero[x1][y1][y2-1];
    }

    //  [x1][y1][x2][y2]　(x1,y1)-(x2,y2)の長方形が含むドーナツ数
    static int num[50][50][50][50];

    for ( int x1=0; x1<W; x1++ )
    for ( int y1=0; y1<H; y1++ )
    for ( int x2=0; x2<W; x2++ )
    for ( int y2=0; y2<H; y2++ )
        num[x1][y1][x2][y2] = 0;

    for ( int w=3; w<=W; w++ )
    for ( int h=3; h<=H; h++ )
    {
        for ( int x1=0; x1<=W-w; x1++ )
        for ( int y1=0; y1<=H-h; y1++ )
        {
            int x2 = x1 + w - 1;
            int y2 = y1 + h - 1;

            int &n = num[x1][y1][x2][y2];

            //  幅・高さどちらかが１小さい長方形が含むドーナツ数
            n = max( n, num[x1+1][y1][x2][y2] );
            n = max( n, num[x1][y1+1][x2][y2] );
            n = max( n, num[x1][y1][x2-1][y2] );
            n = max( n, num[x1][y1][x2][y2-1] );

            //  この長方形自身がドーナツであれば
            //  幅も高さも２小さい長方形が含むドーナツ数＋１
            if ( hzero[x1][y1][x2]  &&  hzero[x1][y2][x2]  &&
                 vzero[x1][y1][y2]  &&  vzero[x2][y1][y2] )
                n = max( n, num[x1+1][y1+1][x2-1][y2-1] + 1 );
        }
    }

    return num[0][0][W-1][H-1];
}