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である
参考にしたサイト
こんな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 ); } }