AOJ 2008 Dragon Fantasy

問題

Dragon Fantasy

解法

全探索＋枝刈り。BFSでときました。枝刈りをするときはループに入らせる前に走査して枝刈りさせないと無駄な探索が入り込んだりすることを知った。

心臓に悪いコード

int n;
int hx, hy, dx, dy, cx[21], cy[21];

double dist(double ax, double ay, double bx, double by){
  return sqrt((ax-bx)*(ax-bx) + (ay-by)*(ay-by));
}

int dfs(int c, double t, int x, int y, int *used){
  if(c == n) return 1;

  rep(i, n){
    if(used[i]) continue;
    if(t + dist(x, y, cx[i], cy[i]) + EPS > dist(dx, dy, cx[i], cy[i])) return 0;
  }

  rep(i, n){
    if(used[i]) continue;
    double nt = dist(x, y, cx[i], cy[i]);

cy[i]);
cy[i]));
    if(t + nt + EPS > dist(dx, dy, cx[i], cy[i])) return 0;
    used[i] = 1;
    if(dfs(c+1, t + nt, cx[i], cy[i], used)) return 1;
    used[i] = 0;
  }
  return 0;
}

int main(){
  while(scanf("%d%d%d%d%d", &n, &hx, &hy, &dx, &dy) && n+hx+hy+dx+dy){
    rep(i, n)
      scanf("%d%d", cx+i, cy+i);;

    int used[21];
    memset(used, 0, sizeof(used));
    if(dfs(0, 0, hx, hy, used)) puts("YES");
    else puts("NO");
  }
  return 0;
}