TopCoder SRM 360 Div1 Easy SumOfSelectedCells

TopCoder

問題

行列が与えられる。
行列から、条件を満たすように成分を選ぶ。

  • 同じ行から二つ以上の成分を選ばない
  • 同じ列から二つ以上の成分を選ばない
  • 上の条件を満たす選び方で、選ぶ個数が最も多くなるように選ぶ

このとき、どのような成分の選び方をしても、成分の和が同じならばCORRECTを、そうでないならINCORRECTを出力せよ。

制約条件

行≦20
列≦20

方針

行列が正方行列でない場合、
縦か横に長い場合、
長いほうの成分は全部同じ数でなくてはならない。
AAAAA
BBBBB
CCCCC
みたいに。


行列が正方行列だったら、
任意の二つの要素を(i,j)(k,l)とすると、
行と列を入れ替えて、(i,l)(k,j)のように成分を選んだとき和が異なっていたらINCORRECT
全ての要素について和が一致したらCORRECT.

ソースコード

class SumOfSelectedCells {
  public:
  string hypothesis(vector <string> table) {
    vector<vi> t;
    int h=table.size(),w;
    rep(i,h){
      stringstream ss(table[i]);
      int a;
      vi v;
      while(ss>>a)v.pb(a);
      t.pb(v);
    }
    w=t[0].size();
    if(h==w){
      rep(i,h)rep(j,w)rep(k,h)rep(l,w)if(t[i][j]+t[k][l]!=t[i][l]+t[k][j])
        return "INCORRECT";
    }
    else if(h>w){
      rep(i,w)rep(j,h)rep(k,h)if(t[j][i]!=t[k][i])return "INCORRECT";
    }
    else{
      rep(i,h)rep(j,w)rep(k,w)if(t[i][j]!=t[i][k])return "INCORRECT";
    }
    return "CORRECT";
  }
};