POJ 1450 Gridland

問題

デカルト座標上にnxmのグリッドがある。グリッドの格子点では上下左右の格子点に加え対角線方向のグリッドにも移動できる。このnxmの格子点について巡回セールスマン問題を解け。

やりかた

巡回セールスマン問題なのでnxm回の辺の移動がある。なので問題は8方向の移動回数である。これは少し実験するとわかるが、n,mの少なくとも一方が偶数であれば上下左右の移動のみで完結でき、そうでなければ一回だけ対角線方向の移動を入れることで完結できる。

以下ソース。

int main(int argc, char **argv){
  int n;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++){
    int H, W;
    scanf("%d %d", &H, &W);
    printf("Scenario #%d:\n", i);
    printf("%.2lf\n\n", H * W + (H * W % 2 ? sqrt((double)2) - 1 : 0));
  }
  return 0;
}