SRM559 Div2 Hard "ToyTrain"
問題
おもちゃの王様がいます。
王様は広大な土地を所有しており、その土地は正方形のグリッドで地区に区切られています。
また、この土地には9人の領主が住んでおり、
いくつかの地区はこれら9人の領主に所有権を与えています。
王様は冬の祭典を開催するために、線路を完成させようと思っています。
線路のピースは以下のような3種類があります。
A型:90度曲がっており、両端は凸になっている。 B型:90度曲がっており、両端は凹になっている。 S型:直線であり、1つの端は凸、もう1つは凹になっている。 イメージ図参照
2つのピースを接続する時は、一端が凸、もう一端が凹になっている必要があります。
現在、いくつかの地区には既に線路のピースが設置されており、
王様はそれを90度単位で回転する事が出来ます。
またS型のピースをピースが置かれていない地区に新規に設置する事が出来ます。
現在のそれぞれの地区の状態が文字列配列のfieldで与えられます。
1文字が1地区の状態を表しており、意味は以下の通りです。
'.' その地区は何も設置されていません。 'A' A型のピースが設置されています。 'B' B型のピースが設置されています。 'S' S型のピースが設置されています。 '1-9' 領主1-9が所有している地区です。
王様は最終的に線路を環状にしたいと考えています。
(環状になった線路は1つでも、複数でもよい)
正確に言えば、各ピースは2つのピースと接続された状態でなければいけません。
そうするためにS型のピースを設置する場合、
そこが領主iが所有している地区であれば、
iだけのお金を払わなくてはなりません。
ただし、領主iに一回お金を払えば、
その領主の所有している地区は好きなだけ線路を設置できます。
領主が所有していない地区であればお金はかかりません。
線路を完成させるための最小費用を返してください。
また、線路が完成させる事が出来ないならば、-1を返してください。
制約
1 <= fieldの要素数 <= 50
1 <= fieldの文字列の長さ <= 50
考えた事
ピースA,Bが置かれた地区で、
このピースをどう回転させたらよいかを考えてみる。
上の地区から線路が来ていた場合、
┛もしくは┗のどちらかで設置するしかない。
上の地区から線路が来ていない場合、
┓もしくは┏のどちらかで設置するしかない。
左の地区から線路が来ていた場合、
┛もしくは┓のどちらかで設置するしかない。
左の地区から線路が来ていない場合、
┗もしくは┏のどちらかで設置するしかない。
ピースSはどうか?
上の地区から線路が来ていた場合、
┃で設置するしかない。
上の地区から線路が来ていない場合、
━で設置するしかない。
左の地区から線路が来ていた場合、
━で設置するしかない。
左の地区から線路が来ていない場合、
┃で設置するしかない。
したがって、設置されているピースをどう回転させるかは、
1つに決まってしまう。
自由に回転させて最小費用を返せといってるけど、
線路の設置の仕方は1つだけなのである・・・
線路は環状になるのか?
設置できるならどの領主の地区を通ったか?
を出せるよう実装すればよい。
ソースコード
class ToyTrain { public: int getMinCost(vector <string> field){ // 金払ったかフラグを初期化 bool pay[10]; memset( pay, false, sizeof(pay) ); // 簡単にするため、最初に空のフィールドを一行追加 ostringstream inStr; for( int i = 0; i < field[0].length(); i++ ){ inStr << '.'; } field.insert( field.begin(), inStr.str() ); int h = field.size(); int w = field[0].length(); bool find = false; for( int y = 1; y < h; y++ ){ char left = '.'; // 左側からこっちに向かってきているレールのタイプ for( int x = 0; x < w; x++ ){ char c = field[y][x]; char p = field[y-1][x]; if( c == 'A' ){ // 同じ型のレールが向かってきていないかチェック if( left == 'A' || p == 'A' ) return -1; if( left == 'B' ){ left = '.'; }else{ left = 'A'; } if( p == 'B' ){ field[y][x] = '.'; }else{ field[y][x] = 'A'; } find = true; }else if( c == 'B' ){ // 同じ型のレールが向かってきていないかチェック if( left == 'B' || p == 'B' ) return -1; if( left == 'A' ){ left = '.'; }else{ left = 'B'; } if( p == 'A' ){ field[y][x] = '.'; }else{ field[y][x] = 'B'; } find = true; }else if( c == 'S' ){ // 左と上方向から同時にレールが向かってきていないかチェック if( left != '.' && p != '.' ) return -1; // レールが向かってきていない場合をチェック if( left == '.' && p == '.' ) return -1; if( p != '.' ){ field[y][x] = p; }else{ field[y][x] = '.'; } }else if( c == '.' ){ // 左と上方向から同時にレールが向かってきていないかチェック if( p != '.' && left != '.' ) return -1; if( p != '.' ) field[y][x] = p; }else{ // 左と上方向から同時にレールが向かってきていないかチェック if( p != '.' && left != '.' ) return -1; if( p != '.' ){ pay[c-'0'] = true; field[y][x] = p; }else{ field[y][x] = '.'; } if( left != '.' ){ pay[c-'0'] = true; } } } // 右に向かうレールが取り残されていないかチェック if( left != '.' ) return -1; } // レールが設置されていなかったかチェック if( !find ) return -1; // 最後の行に下方向へのレールがなかったかチェック for( int x = 0; x < w; x++ ){ if( field[h-1][x] != '.' ) return -1; } // 払ったお金を計算 int res = 0; for( int i = 1; i <= 9; i++ ){ if( pay[i] ) res += i; } return res; } };