SRM550 Div2 Hard

1000

トポロジカルソートする。

const int N = CHAR_MAX + 1;
bool g[N][N];

const string error = "ERROR!";

string tsort(const vector<char> &C)
{
  string ord;
  priority_queue< char, vector<char>, greater<char> > u;

  int deg[N];
  fill(deg, deg + N, 0);

  for (int i = 0; i < C.size(); ++i) {
    for (int j = 0; j < C.size(); ++j) {
      int src = C[i];
      int dst = C[j];
      if (g[src][dst]) ++deg[dst];
    }
  }

  for (int i = 0; i < C.size(); ++i) {
    if (deg[(int)C[i]] == 0) u.push(C[i]);
  }

  while (u.size()) {
    int n = u.top();
    u.pop();
    ord.push_back(n);
    for (int m = 0; m < N; ++m) {
      if (g[n][m]) {
        g[n][m] = false;
        if (--deg[m] == 0) u.push(m);
      }
    }
  }

  if (ord.size() != C.size()) ord = error;
  return ord;
}

class TopView {
public:
  string findOrder(vector <string> G)
  {
    map<char, int> mnH, mnW;
    map<char, int> mxH, mxW;

    vector<char> v;

    const int H = G.size();
    const int W = G[0].size();

    const int inf = 1 << 29;

    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        char c = G[i][j];
        if (c == '.') continue;
        v.push_back(c);
        if (mnH.count(c) == 0) mnH[c] = +inf;
        if (mnW.count(c) == 0) mnW[c] = +inf;
        if (mxH.count(c) == 0) mxH[c] = -inf;
        if (mxW.count(c) == 0) mxW[c] = -inf;
        mnH[c] = min(mnH[c], i);
        mnW[c] = min(mnW[c], j);
        mxH[c] = max(mxH[c], i);
        mxW[c] = max(mxW[c], j);
      }
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    fill(&g[0][0], &g[N - 1][N], false);
    for (int k = 0; k < v.size(); ++k) {
      int c = v[k];
      for (int i = mnH[c]; i <= mxH[c]; ++i) {
        for (int j = mnW[c]; j <= mxW[c]; ++j) {
          if (G[i][j] == '.') return error;
          int d = G[i][j];
          g[c][d] = true;
        }
      }
      g[c][c] = false;
    }

    return tsort(v);
  }
};