WARush

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

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;
    }
};