SRM550 Div2 Hard

1000

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

view plainprint?

1. const int N = CHAR_MAX + 1;  
2. bool g[N][N];  
3.   
4. const string error = "ERROR!";  
5.   
6. string tsort(const vector<char> &C)  
7. {  
8.   string ord;  
9.   priority_queue< char, vector<char>, greater<char> > u;  
10.   
11.   int deg[N];  
12.   fill(deg, deg + N, 0);  
13.   
14.   for (int i = 0; i < C.size(); ++i) {  
15.     for (int j = 0; j < C.size(); ++j) {  
16.       int src = C[i];  
17.       int dst = C[j];  
18.       if (g[src][dst]) ++deg[dst];  
19.     }  
20.   }  
21.   
22.   for (int i = 0; i < C.size(); ++i) {  
23.     if (deg[(int)C[i]] == 0) u.push(C[i]);  
24.   }  
25.   
26.   while (u.size()) {  
27.     int n = u.top();  
28.     u.pop();  
29.     ord.push_back(n);  
30.     for (int m = 0; m < N; ++m) {  
31.       if (g[n][m]) {  
32.         g[n][m] = false;  
33.         if (--deg[m] == 0) u.push(m);  
34.       }  
35.     }  
36.   }  
37.   
38.   if (ord.size() != C.size()) ord = error;  
39.   return ord;  
40. }  
41.   
42. class TopView {  
43. public:  
44.   string findOrder(vector <string> G)  
45.   {  
46.     map<char, int> mnH, mnW;  
47.     map<char, int> mxH, mxW;  
48.   
49.     vector<char> v;  
50.   
51.     const int H = G.size();  
52.     const int W = G[0].size();  
53.   
54.     const int inf = 1 << 29;  
55.   
56.     for (int i = 0; i < H; ++i) {  
57.       for (int j = 0; j < W; ++j) {  
58.         char c = G[i][j];  
59.         if (c == '.') continue;  
60.         v.push_back(c);  
61.         if (mnH.count(c) == 0) mnH[c] = +inf;  
62.         if (mnW.count(c) == 0) mnW[c] = +inf;  
63.         if (mxH.count(c) == 0) mxH[c] = -inf;  
64.         if (mxW.count(c) == 0) mxW[c] = -inf;  
65.         mnH[c] = min(mnH[c], i);  
66.         mnW[c] = min(mnW[c], j);  
67.         mxH[c] = max(mxH[c], i);  
68.         mxW[c] = max(mxW[c], j);  
69.       }  
70.     }  
71.   
72.     sort(v.begin(), v.end());  
73.     v.erase(unique(v.begin(), v.end()), v.end());  
74.   
75.     fill(&g[0][0], &g[N - 1][N], false);  
76.     for (int k = 0; k < v.size(); ++k) {  
77.       int c = v[k];  
78.       for (int i = mnH[c]; i <= mxH[c]; ++i) {  
79.         for (int j = mnW[c]; j <= mxW[c]; ++j) {  
80.           if (G[i][j] == '.') return error;  
81.           int d = G[i][j];  
82.           g[c][d] = true;  
83.         }  
84.       }  
85.       g[c][c] = false;  
86.     }  
87.   
88.     return tsort(v);  
89.   }  
90. };  

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