naoya_t@topcoder

SRM434 Div1 Easy: FindingSquareInTable

過去問, 練習 | 04:12 |

• テーブルの途中で数字列が終わるケースのチェックを加えただけでSysTest通った

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

class FindingSquareInTable {
  set<int> psqs;
  bool psq(int n){ return found(psqs,n) ? true : false; }
 public:
  int findMaximalSquare(vector<string> table) {
    for(int i=0;i<=31622; i++) psqs.insert(i*i);

    int maxn = -1;
    int h=sz(table), w=sz(table[0]);
	vector<vector<int> > t(h);
    rep(i,h) { t[i].resize(w); rep(j,w) t[i][j] = table[i][j] - '0'; }
    rep(j0,h) rep(i0,w){
      for(int sy=-(h-1);sy<=h-1;sy++){
        for(int sx=-(w-1);sx<=w-1;sx++){
          int j=j0, i=i0;
          int n=t[j][i];
          if(sx==0 && sy==0) goto jm;
          while(true){
            i+=sx; j+=sy;
            if (i < 0 || w <= i || j < 0 || h <= j) break;
            n = n*10 + t[j][i];
            if (psq(n)) maxn = max(maxn,n); // ←この１行
          }
       jm:
          if (psq(n)) maxn = max(maxn,n);
        }
      }
    }
    return maxn;
  }
};