SRM 505 Div1 easy RectangleArea

topcoder

問題概要

最大50*50に分割されたグリッドが与えられる。
それぞれのセルの大きさは異なっている。
いくつかのセルの面積が最初から明らかになっている。
明らかになっているセルの場所が与えられる。
あと最低いくつのセルの面積を知ることができれば、
全体の面積をしることができるか。

解法

union find
Hを行数。
Wを列数とする。
行、列をノードとする。
今現状明らかになっている場所の行と列を同じグループにする。
今のグループ数-1が答えになる。

解法の説明

1 なぜ、同一のグループに含まれる行、列で表せるセルの面積は求められるか。

H * W = (R0 + R1 + ... RH) * (C0 + C1 + ... CW)
と表すとする。
Riはi行目の行間
Ciはi列目の列間
(0, 0)の面積がわかると、
R0 * C0 = A00
となり、R0とC0は相互に置き換えることができます。
この相互互換可能な行、列のグループをUnionFind木で表すことにします。
面積がわかる度に、そのセルに対応する行、列をまとめます。
ある相互互換可能な行i、列jがあったとして、
行iと相互互換可能な行、列の集合すべては、列jと相互互換可能になります。
行jと相互互換可能な行、列の集合すべてについても同様です。
ある、面積Aijが不明だとします。

  • 行i, 列jが同一のグループだとする。

行i, 列jが同一のグループだとすると、Ri, Cjはそれぞれ同じグループのどの行、列とも変換が可能である。
同一なグループでは必ず面積がすでに明らかになっている行、列の組み合わせが
必ず少なくとも一つ含まれている。よってその面積を求めることが可能。

  • 行i, 列jが違うグループだとする。

行i, 列jが違うグループだとすると、Aijは今までに明らかになっていないことになる。
行iと同じグループに属する行、列(tとする)に変換しても、同じグループに属していないことから、
RtCjは求めることができない。
同様に、列jを入れ替えても、行iと列jが違うグループであることから、積を求めることが不可能。

2 なぜ、今のグループ数-1が答えになるのか。

最終的にグループを一つにまとめれば、1から全体の面積を求めることが可能。
二つのグループを一つにまとめるには片方だけに含まれる行iともう片方だけに含まれる列jのセルの面積Rijがわかれば
一つにまとめることができる。
なにも手を加えずまとめることはできず、すべてが同じグループに属さない限り全体の面積を求めることが不可能なことから、
これが最小手である。

ソース

class DisJointSet{
public:
  vector<int> v;
  DisJointSet(int n){
    v = vector<int>(n);
    rep(i, n)v[i] = i;
  }
  int find(int x){
    if(v[x] == x)return x;
    else return v[x] = find(v[x]);
  }
  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    v[x] = y;
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }
};
class RectangleArea {
public:                 
  int minimumQueries(vector <string> k) {
    int H = k.size();
    int W = k[0].length();
    DisJointSet S(H + W);
    rep(i, H){
      rep(j, W){
        if(k[i][j] == 'Y'){
          S.unite(i, H+j);
        }
      }
    }
    set<int> ans;
    rep(i, H+W){
      ans.insert(S.find(i));
    }
    return ans.size()-1;
  }
};