SRM559 Div2 Hard(1000) ToyTrain - kusano

実は線路の引き方は高々1通りしかない。

左上から順にカーブを見ていき、例えば、そのカーブに上から線路が繋がっていて左から繋がっていなければ『┗』、上からも左からも線路が繋がっていなければ『┏』。カーブの向きを決めたら、右や下に線路が繋がっているならば伸ばす。

線路が引けるかどうか調べて、必要な金額を求める。

#include <string>
#include <vector>
#include <set>
#include <numeric>
using namespace std;

class ToyTrain{public:
int getMinCost( vector <string> field )
{
    int h = (int)field.size();
    int w = (int)field[0].size();

    bool ok = false;
    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
        if ( field[y][x]=='A' || field[y][x]=='B' )
            ok = true;
    if ( !ok )
        return -1;

    //  カーブの向きを決め、直線を置く
    vector<string> F(h,string(w,' '));
    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
    if ( field[y][x]=='A' || field[y][x]=='B' )
    {
        //  上か左に線路があるか
        bool tv = y>0 && (
                    F[y-1][x]=='V' ||
                    F[y-1][x]=='A' ||
                    F[y-1][x]==',' ||
                    F[y-1][x]=='r' );
        bool th = x>0 && (
                    F[y][x-1]=='>' ||
                    F[y][x-1]=='<' ||
                    F[y][x-1]=='r' ||
                    F[y][x-1]=='`' );

        //  線路の正負が一致しているか
        if ( tv &&
             ( ( F[y-1][x]==',' || F[y-1][x]=='r' ) && field[y-1][x]==field[y][x] ||
               ( F[y-1][x]=='V' && field[y][x]=='A' ) ||
               ( F[y-1][x]=='A' && field[y][x]=='B' ) ) )
            return -1;
        if ( th &&
             ( ( F[y][x-1]=='r' || F[y][x-1]=='`' ) && field[y][x-1]==field[y][x] ||
               ( F[y][x-1]=='>' && field[y][x]=='A' ) ||
               ( F[y][x-1]=='<' && field[y][x]=='B' ) ) )
            return -1;

        //  カーブの向きを決定      
        F[y][x] = "r,`'"[2*(tv?1:0)+(th?1:0)];
        if ( F[y][x]=='r' || F[y][x]=='`' )
            for ( int xx=x; ; )
            {
                xx++;
                if ( xx>=w )  return -1;
                if ( field[y][xx]=='A' || field[y][xx]=='B' )  break;
                if ( F[y][xx]!=' ' )  return -1;
                F[y][xx] = field[y][x]=='A' ? '>' : '<';
            }
        if ( F[y][x]=='r' || F[y][x]==',' )
            for ( int yy=y; ; )
            {
                yy++;
                if ( yy>=h )  return -1;
                if ( field[yy][x]=='A' || field[yy][x]=='B' )  break;
                if ( F[yy][x]!=' ' )  return -1;
                F[yy][x] = field[y][x]=='A' ? 'V' : 'A';
            }
    }
    //cout << endl;
    //for ( int y=0; y<h; y++ )
    //  cout << F[y] << endl;

    //  余計な線路があったら不可
    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
        if ( F[y][x]==' ' && field[y][x]=='S' )
            return -1;

    //  必要な金額を求める
    set<int> S;
    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
        if ( F[y][x]!=' ' && '1'<=field[y][x] && field[y][x]<='9' )
            S.insert(field[y][x]-'0');

    return accumulate(S.begin(),S.end(),0);
}};