WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM577 Div1 Medium "EllysChessboard"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12527

エリーは8 * 8のマスを持つ、ごく普通のチェスボードを持っている。
彼女は小石をいくつか、そのマスへ置きたいと思っている。
あなたには String[] board が与えられる。
boardのi番目の要素のj番目の文字はボードの( i, j )マスに対応している。
文字が ' # ' である場合、
そのマスは彼女が小石を置きたがっているマスであることを示し、
文字が ' . 'である場合、
そうではない事を示す。

初め、チェスボードには小石は1つも乗っていない。
エリーは小石を一つ一つ置いていく。
小石を置いたときのコストは次のようになっている。
それが最初に置いた小石であれば、コストはかからない。
そうでなければ、既に小石が置かれている中の最も遠いマスの、
マンハッタン距離がコストとなる。
※( x1, y1 ) ( x2, y2 ) のマンハッタン距離は| x1 - x2 | + | y1 - y2 |である。

小石を置ききったときの、最小コストを返せ。

制約

ボードは8 * 8である


参考にしたサイト

Barty's Blog - 菜鳥成長記

こんなDP思いつかんて・・・
というか、これでなんで正しくなるのかすら分かってない。

マンハッタン距離がでてくる = 座標を45度回転させることを考えてみる
っていう事は覚えておいたほうがいいっぽい。

ソースコード

const int INF = 10000;

class EllysChessboard {
public:

    int memo[15][15][15][15]; 
    bool dat[15][15]; // dat[i][j] = (i, j)は'#'か?

    // a b c の最大値を返す
    int max3( int a, int b, int c ){
        return max( a, max( b, c ) );
    }

    // 幅ax bx, 高さay byの範囲の小石を追加したときの
    // 最小コストを返す。
    int dfs( int ax, int ay, int bx, int by ){
        int& m = memo[ax][ay][bx][by];

        if( ax > bx || ay > by ) return INF;
        if( ax == bx && ay == by ) return 0;

        // メモってればそれを返す
        if( m != -1 ) return m;
        
        m = INF;
        // 左端を広げる
        int cost = dfs( ax+1, ay, bx, by );
        for( int i = ay; i <= by; i++ ){
            if( dat[ax][i] ) cost += max3( bx-ax, i-ay, by-i );
        }
        m = min( m, cost );
        // 右端を広げる
        cost = dfs( ax, ay, bx-1, by );
        for( int i = ay; i <= by; i++ ){
            if( dat[bx][i] ) cost += max3( bx-ax, i-ay, by-i );
        }
        m = min( m, cost );
        // 上端を広げる
        cost = dfs( ax, ay+1, bx, by );
        for( int i = ax; i <= bx; i++ ){
            if( dat[i][ay] ) cost += max3( by-ay, i-ax, bx-i );
        }
        m = min( m, cost );
        // 下端を広げる
        cost = dfs( ax, ay, bx, by-1 );
        for( int i = ax; i <= bx; i++ ){
            if( dat[i][by] ) cost += max3( by-ay, i-ax, bx-i );
        }
        m = min( m, cost );

        return m;
    }

    int minCost(vector <string> board){
        memset( dat, false, sizeof(dat) );
        memset( memo, -1, sizeof(memo) );
        // ナナメにする!
        for( int y = 0; y < 8; y++ ){
            for( int x = 0; x < 8; x++ ){
                dat[y+x][y-x+7] = board[y][x] == '#';
            }
        }        

        return dfs( 0, 0, 14, 14 );        
    }
}