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しかないので、更新方向は次のようにする。
着目するマスを黒いマスにすると、必要な白マスの情報は次のようななる。
各黒マスにおいて、
・タイルを置かない
・左上、左下、右上、右下の白マスを使ってタイルを置く
の5パターンを試し、最も数の多いものを選んでいけばよい。
タイルを置かない場合
上図のようになるので、着目している黒マスと同じ高さの白マスの情報を
「タイルが置かれてないよ!」と更新してあげる。
左上、左下の白マスを使ってタイルを置く場合
例えば左上を使うと上図のようになるので、
上の白マスを「タイルが置かれているよ!」と更新してあげる。
右上、右下の白マスを使ってタイルを置く場合
例えば右上を使うと上図のようになるので、
上と右の白マスを「タイルが置かれているよ!」と更新してあげる。
事後
始め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 ); } };