SRM 550 Div2 Hard TopView

問題

グリッド上にタイルが敷かれており、タイルの色は数字かアルファベットで表される。タイルは必ずXY軸に平行な矩形の形で敷き詰められる。タイルは別のタイルの上に積み重ねていくことができ、各色のタイルは一度しか敷かれることがない。タイルを鳥瞰した時の見える色が与えられた時、タイルが重なっている順番を返せ。複数ある場合は色を表す文字が辞書式最小になるものを返せ。存在しない場合は"ERROR!"を返せ。

やりかた

ある色のタイルが敷かれている領域を囲む矩形を求め、これをすべての色についておこなう。続いて、色を２色取り出し、どちらの矩形が上に来ているかを調べることによって、その２色のうちどちらのタイルが上に来ているかがわかる。これをすべての色について調べることで、すべての色について上下関係がわかる。
上下関係は有向グラフとして表現できるので、すべての上下関係がわかれば、あとはグラフの順序を守りつつ辞書式最小に色を取り出していけばよいことになる。これはトポロジカルソートで行うことができる。トポロジカルソートできなければERROR!を返す。また、穴('.')の開いた矩形であってもERROR!を返す。

辞書式最小のトポロジカルソートのやり方がわからず、kusano_progさんのコードを参考にしました。

以下ソース。きったない。

struct rect{
  char c;
  int y, x;
  int ny, nx;
  bool operator<(const rect &r)const{
    return c < r.c;
  }
};

class TopView {
public:
  vector<int> topological(vector<vector<bool> > E){
    int n = 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;
  }
  string findOrder(vector <string> grid) {
    string result;
    set<char> use;
    string ret;
    vector<rect> t;

    int H = grid.size();
    int W = grid[0].size();
    for(int i = 0; i < H; i++)
      for(int j = 0; j < W; j++)
	if(grid[i][j] != '.') use.insert(grid[i][j]);

    //その色のタイルを囲う矩形を調べる
    for(set<char>::iterator it = use.begin(); it != use.end(); it++){
      int a = 1000, b = 1000, c = 0, d = 0;
      for(int i = 0; i < H; i++){
	for(int j = 0; j < W; j++){
	  if(grid[i][j] == *it){
	    a = min(a, i); b = min(b, j);
	    c = max(c, i); d = max(d, j);
	  }
	}
      }
      rect tmp;
      tmp.c = *it;
      tmp.y = a;
      tmp.x = b;
      tmp.ny = c;
      tmp.nx = d;
      t.push_back(tmp);
      //矩形に穴があればエラー
      for(int i = a; i <= c; i++)
	for(int j = b; j <= d; j++)
	  if(grid[i][j] == '.') return "ERROR!";
    }
    int N = t.size();
    vector<vector<bool> > edge(N, vector<bool>(N, false));
    map<char, int> num;

    //矩形の上下関係を調べる
    for(int i = 0 ; i < N ; i++) num[t[i].c] = i;
    for(int i = 0 ; i < N ; i++){
      for(int j = 0; j < N; j++){
	if(i == j) continue;
	for(int y = t[i].y; y <= t[i].ny; y++){
	  for(int x = t[i].x; x <= t[i].nx; x++){
	    if(grid[y][x] == '.') return "ERROR!";
	    if(grid[y][x] == t[j].c){
	      edge[i][j] = true;
	    }
	  }
	}
      }
    }

    //トポロジカルソートして順番に取り出す
    vector<int> V = topological(edge);
    if(V.empty()) return "ERROR!";
    else{
      for(int i = 0; i < (int)V.size(); i++)
	ret += t[V[i]].c;
    }
    return ret; 
  }
};

トポロジカルソートをあいまいなまま今までやってきていたのでここできちんと理解できたのは収穫。