WARush

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

SRM575 Div2 Hard "TheTilesDivTwo"

問題

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

マスが黒の白に塗りわけられたチェスボードがある。
このチェスボードの行・列には0から始まる数字が付けられている。
行番号をi 列番号をj としたとき、
i+jが偶数ならば黒のマス、i+jが奇数ならば白のマスとなっている。

チェスボードのいくつかのマスには、既にチェスの駒が置かれている。


今、L字型のタイルを無限に持っている。
そのタイルの形は、ちょうどチェスボードのマスを3つL字にくっつけたようになっている。

OO
O

このタイルを下記のようなルールに基づいてチェスボードに置いていきたい。

タイルは90度単位で回転できる。
タイルはチェスボードの3つのセルにピッタリ合わせて置かなくてはならない。
タイル同士を重ねて置くことはできない。
すでに駒が置かれているマスには置く事ができない。
タイルのコーナー部分は黒のマスに置かなくてはならない。

チェスボードの幅、高さ、駒が置かれているマスの情報が与えられる。
上記のルールに従ったとき、置く事ができるタイルの最大の数を返せ。

制約

1 <= チェスボードの高さ <= 4
1 <= チェスボードの幅 <= 47


考えた事

蟻本のドミノ敷き詰めを発展させた問題だな(蟻本 P177)

高さが4しかないので、更新方向は次のようにする。
f:id:Ekaing:20130408130943j:plain

着目するマスを黒いマスにすると、必要な白マスの情報は次のようななる。
f:id:Ekaing:20130408131107j:plain

各黒マスにおいて、
・タイルを置かない
・左上、左下、右上、右下の白マスを使ってタイルを置く
の5パターンを試し、最も数の多いものを選んでいけばよい。

タイルを置かない場合

f:id:Ekaing:20130408131339j:plain
上図のようになるので、着目している黒マスと同じ高さの白マスの情報を
「タイルが置かれてないよ!」と更新してあげる。

左上、左下の白マスを使ってタイルを置く場合

f:id:Ekaing:20130408131617j:plain
例えば左上を使うと上図のようになるので、
上の白マスを「タイルが置かれているよ!」と更新してあげる。

右上、右下の白マスを使ってタイルを置く場合

f:id:Ekaing:20130408131921j:plain
例えば右上を使うと上図のようになるので、
上と右の白マスを「タイルが置かれているよ!」と更新してあげる。

事後

始めDPでやったら頭が混乱。コードがぐちゃぐちゃになってひどいもんだった。
結局、実装完了までに2時間・・・
Submitするには3,40分でできないとなぁ


ソースコード

class TheTilesDivTwo {
public:

    vector<string> board;
    int H, W;

    int memo[50][5][1<<4];

    // この白マスにタイル置ける?
    bool chk( int x, int y, int bit ){
        if( x < 0 || W <= x || y < 0 || H <= y ) return false;
        if( board[y][x] == 'X' ) return false;
        return (bit & 1 << y) == 0;
    }

    // このマスにタイル置ける?
    bool chk( int x, int y ){
        if( x < 0 || W <= x || y < 0 || H <= y ) return false;
        if( board[y][x] == 'X' ) return false;
        return true;
    }

    // (x, y) - 着目している黒マス bit - 白マスの情報
    int dfs( int x, int y, int bit ){
        if( y >= H ){
            x++;
            y = (x % 2) ? 1 : 0;
        }
        if( x >= W ) return 0;
        
        int& m = memo[x][y][bit];
        if( m != -1 ) return m;

        
        // 置かない
        int newBit = bit & ~(1 << y);
        int res = dfs( x, y+2, newBit );

        if( chk( x, y ) ){
            // 左上
            if( chk( x-1, y, bit ) && chk( x, y-1, bit ) ){
                int newBit = bit | 1 << (y-1);
                res = max( res, dfs( x, y+2, newBit ) + 1 );
            }

            // 左下
            if( chk( x-1, y, bit ) && chk( x, y+1, bit ) ){
                int newBit = bit | 1 << (y+1);
                res = max( res, dfs( x, y+2, newBit ) + 1 );
            }

            // 右上
            if( chk( x+1, y ) && chk( x, y-1, bit ) ){
                int newBit = bit | (1 << y) | (1 << (y-1));
                res = max( res, dfs( x, y+2, newBit ) + 1 );
            }

            // 右下
            if( chk( x+1, y ) && chk( x, y+1, bit ) ){
                int newBit = bit | (1 << y) | (1 << (y+1));
                res = max( res, dfs( x, y+2, newBit ) + 1 );
            }
        }        

        return m = res;
    }

    int find(vector <string> _board){
        board = _board;
        H = board.size();
        W = board[0].length();

        // 高さが1だったら絶対置けない
        if( H == 1 ) return 0;

        // メモリセット
        for( int x = 0; x < W; x++ ){
            for( int y = 0; y < H; y++ ){
                for( int bit = 0; bit < 1 << H; bit++ ){
                    memo[x][y][bit] = -1;
                }
            }
        }        

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