SRM574 Div1 Hard "Tunnels"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12476
訳
地下にいくつかのトンネルが掘られている。
それらのトンネルは直線上に掘られているため、地下の状態を2次元として考える。
地下は1メートル四方のセルに分割されている。
それぞれのトンネルは、複数のセルから構成されており、
下記のルールにしたがって掘られている。
- 最初は一番浅い所にあるセルを掘る
- 最後に掘ったセルから右・左・下のどれかのセルを掘っていく
- ただし、既に他で掘られていたセルと辺を共有しているセルは掘る事が出来ない
トンネルの例
***GROUND*** .X..X...X.X. .X....XXX.X. .XXX..X...X. ...X..X.XXX. .XXX..X..... ......XXXX..
だめなトンネルの例を下記に示す。
1番目の例は、一番浅いセルから掘られていないのでダメ
2番目の例は、上に向かって掘っているからダメ
3番目の例は、既に掘られていたセルと、辺を共有したセルを掘ってるからダメ
4番目の例は、2つのトンネルのセルに、辺を共有しているものがあるのでダメ
**********GROUND********** ... X... X.. X....X .X. X... XXX XXXXXX ... X.X. .XX ..XX.. ... XXX. ... ..X...
地下には左右・深さで無限のセルがあると仮定する事ができる。
地下の状態の断片が高さH、幅Wだけ与えられるので、最小いくつのトンネルが掘られているかを返せ。
制約
1 <= H, W <= 50
事後
トンネルの場合わけが複雑すぎぃ!!
ソースコード
vector<string> frame; int H, W; bool chk[55][55]; int tunnelNum; bool isRightUp[55]; bool isLeftUp[55]; bool isRightDown[55]; bool isLeftDown[55]; bool isLR[55]; int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 }; class Tunnels { public: void getLast( int x, int y, int* lx, int* ly ){ chk[y][x] = true; *lx = x; *ly = y; for( int d = 0; d < 4; d++ ){ int tx = x + dx[d], ty = y + dy[d]; if( tx < 0 || W <= tx || ty < 0 || H <= ty ) continue; if( chk[ty][tx] ) continue; if( frame[ty][tx] == 'X' ){ getLast( tx, ty, lx, ly ); } } } void input( vector<string>& _frame ){ frame = _frame; H = frame.size(); W = frame[0].length(); // リセット tunnelNum = 0; for( int i = 0; i < 55; i++ ){ isRightUp[i] = isLeftUp[i] = isRightDown[i] = isLeftDown[i] = isLR[i] = false; } for( int y = 0; y < H; y++ ) for( int x = 0; x < W; x++ ){ if( frame[y][x] != 'X' || chk[y][x] ) continue; chk[y][x] = true; tunnelNum++; // 両端の位置を取得 int ex1 = x, ey1 = y, ex2 = x, ey2 = y; bool first = true; for( int d = 0; d < 4; d++ ){ int tx = x + dx[d], ty = y + dy[d]; if( tx < 0 || W <= tx || ty < 0 || H <= ty ) continue; if( frame[ty][tx] != 'X' ) continue; if( first ){ getLast( tx, ty, &ex1, &ey1 ); first = false; }else{ getLast( tx, ty, &ex2, &ey2 ); } } const int LE = 0, RE = W - 1; // 左端と右端 if( ey1 == 0 && ey2 == 0 ){ if( ex1 > ex2 ) swap( ex1, ex2 ); if( ex1 == LE && ex2 == RE ){ isLR[0] = true; }else if( ex1 == LE ){ isLeftDown[0] = true; }else if( ex2 == RE ){ isRightDown[0] = true; } continue; } if( ey1 > ey2 ){ swap( ex1, ex2 ); swap( ey1, ey2 ); } if( ey1 == 0 ){ if( ex2 == LE ){ isLeftDown[ey2] = true; }else if( ex2 == RE ){ isRightDown[ey2] = true; } continue; } if( ey1 == ey2 ){ if( ex1 > ex2 ) swap( ex1, ex2 ); if( ex1 == LE && ex2 == RE ){ isLR[ey1] = true; }else if( ex1 == LE ){ isLeftUp[ey1] = true; }else if( ex2 == RE ){ isRightUp[ey1] = true; } continue; } if( ex1 == LE ){ isLeftUp[ey1] = true; if( ex2 == RE ){ isRightDown[ey2] = true; }else if( ex2 == LE && ey1+2 <= ey2 ){ isLeftDown[ey2] = true; } }else{ isRightUp[ey1] = true; if( ex2 == LE ){ isLeftDown[ey2] = true; }else if( ex2 == RE && ey1+2 <= ey2 ){ isRightDown[ey2] = true; } } } } int memo[55][55][55]; /* * 最大いくつ、入り口と入り口を繋げる事ができるか? * * i - 深さ * L - 左に何本のトンネルが下りてきているか * R - 右に何本のトンネルが下りてきているか */ int getMaxPair( int i, int L, int R ){ if( i >= H ) return 0; int& m = memo[i][L][R]; if( m != -1 ) return m; // ..... // XXXXX // ..... if( isLR[i] ){ // X...... // XXXXXXX // ......X int l = L > 0 ? L - 1 : 0; int add = L > 0 ? 1 : 0; int res1 = getMaxPair( i+1, l, R+1 ) + add; // ......X // XXXXXXX // X...... int r = L > 0 ? R - 1 : 0; add = R > 0 ? 1 : 0; int res2 = getMaxPair( i+1, L+1, r ) + add; return m = max( res1, res2 ); } // それ以外 int add = 0; if( isLeftDown[i] ) L++; if( isRightDown[i] ) R++; if( isLeftUp[i] && L > 0 ){ L--; add++; } if( isRightUp[i] && R > 0 ){ R--; add++; } return m = getMaxPair( i+1, L, R ) + add; } int solve(){ if( W == 1 ) return tunnelNum ? 1 : 0; memset( memo, -1, sizeof(memo) ); return tunnelNum - getMaxPair( 0, 0, 0 ); } int minimumTunnels(vector <string> _frame){ input( _frame ); return solve(); } };