naoya_t@topcoder

SRM212 Div2 Hard: LargestCircle

過去問, 練習, Tutorials | 04:27 |

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例（その２）。

• とりうる中心＆半径について全て試してみた
• 普通にコンパイルするとTest Case #6で2.6秒かかったが、-O3 で161msec。余裕
• 718.97points (19'25''), Passed System Test

class LargestCircle {
  int in(int x,int y,int r, int u,int v){
    return (u-x)*(u-x) + (v-y)*(v-y) - r*r;
  }
 public:
  int radius(vector<string> grid) {
    int h=sz(grid), w=sz(grid[0]);
    if (h==1 || w==1) return 0;
    int R = 0;
    for(int x=1;x<=w-1;x++){
      int dxmax=min(x,w-x);
      for(int y=1;y<=h-1;y++){
        int dymax=min(y,h-y);
        int rmax=min(dxmax,dymax);
        for(int r=rmax;r>=1;r--){
          bool ok=true;
          for(int u=0;u<w;u++){
            for(int v=0;v<h;v++){
              if(grid[v][u]=='#'){
                int a = in(x,y,r, u,v);
                int b = in(x,y,r, u+1,v);
                int c = in(x,y,r, u,v+1);
                int d = in(x,y,r, u+1,v+1);
                if ((a>=0 && b>=0 && c>=0 && d>=0) || (a<=0 && b<=0 && c<=0 && d<=0)) {
                } else {
                  ok=false; goto out;
                }
              }
            }
          }
       out:
          if (ok) R>?=r; // ←コンパイル時にwarning出るね
        }
      }
    }
    return R;
  }
};

• >?= なのか <?= なのかぱっと分からないので両方試したのは内緒。
• コンパイル時にwarning出るが構わない

LargestCircle.cpp: In member function ‘int LargestCircle::radius(std::vector<std::string, std::allocator<std::string> >)’:

LargestCircle.cpp:75: warning: minimum/maximum operators are deprecated