SRM550 Div2 Hard(1000) TopView

TopView

文字aのx軸方向とy軸方向の範囲内に、文字bがあるならば、bはaの上にある。bがaの上にある場合に、aからbに辺を張ったグラフを作り、トポロジカルソートすると順番が得られる。

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

//  辞書順最小になるようにトポロジカルソート　O(n^3)
vector<int>topological(vector<vector<bool> >E)
{
    int n=(int)E.size();
    vector<bool>V(n);
    vector<int>R;
    for(int i=0;i<n;i++){
        int c=-1;
        for(int j=0;j<n&&c==-1;j++)if(!V[j]){
            bool f=true;
            for(int k=0;k<n&&f;k++)
                if (!V[k]&&E[k][j])
                    f=false;
            if(f)c=j;
        }
        if(c==-1)
            return vector<int>();
        V[c]=true;
        R.push_back(c);
    }
    return R;
}

class TopView{public:
string findOrder( vector <string> grid )
{
    int W = (int)grid[0].size();
    int H = (int)grid.size();

    //  添え字の文字が存在するか
    vector<bool> exist(128);
    //  添え字の文字の最左・最上・最右・最下の位置
    vector<int> minx(128,W-1);
    vector<int> miny(128,H-1);
    vector<int> maxx(128,0);
    vector<int> maxy(128,0);

    for ( int y=0; y<(int)grid.size(); y++ )
    for ( int x=0; x<(int)grid[y].size(); x++ )
    if ( grid[y][x]!='.' )
    {
        char c = grid[y][x];
        exist[c] = true;
        minx[c] = min(minx[c],x);
        miny[c] = min(miny[c],y);
        maxx[c] = max(maxx[c],x);
        maxy[c] = max(maxy[c],y);
    }

    //  .
    exist['.'] = true;
    minx['.'] = 0;
    miny['.'] = 0;
    maxx['.'] = W-1;
    maxy['.'] = H-1;

    //  E[x][y]: yがxの上にある
    vector<vector<bool> > E(128,vector<bool>(128));
    
    for ( int y=0; y<(int)grid.size(); y++ )
    for ( int x=0; x<(int)grid[y].size(); x++ )
    {
        char c = grid[y][x];
        for ( int i=0; i<128; i++ )
            if ( i!=c && exist[i] &&
                 minx[i]<=x && x<=maxx[i] &&
                 miny[i]<=y && y<=maxy[i] )
                E[i][c] = true;
    }

    vector<int> V = topological(E);

    string ans;
    if ( V.empty() )
        ans = "ERROR!";
    else
        for ( int i=0; i<128; i++ )
            if ( exist[V[i]] && V[i]!='.' )
                ans += (char)V[i];
    return ans;
}};