SRM 659 Div2 Medium PublicTransit

問題

RC列の2次元平面上にいて,隣接するセルに移動できる. ある点からある点に即座に移動できるテレポート地点を1つだけ作ることが出来る. 任意のポジション間の最短距離の最大をDとすると, Dの最小値を求める問題.

解答

0 <= R, C <= 10と小さいので全てのテレポート地点を考え全探索する.

class PublicTransit
{
public:
  int minimumLongestDistance(int R, int C)
    {
      int i1, j1, i2, j2, i3, j3, i4, j4;
      int k1, k2, k3, k4;
      int res = R + C;
      int W = R*C;
      for (k1 = 0; k1 < W; k1++){
        i1 = k1 / C;
        j1 = k1 % C;
        for (k2 = k1; k2 < W; k2++){
          i2 = k2 / C;
          j2 = k2 % C;
          int mcost = 0;
          for (k3 = 0; k3 < W; k3++){
            i3 = k3 / C;
            j3 = k3 % C;
            for (k4 = k3; k4 < W; k4++){
              i4 = k4 / C;
              j4 = k4 % C;
              int normal_cost = abs(i3-i4) + abs(j3-j4);
              int teleport_cost1 = abs(i3-i2) + abs(j3-j2) + abs(i4-i1) + abs(j4-j1);
              int teleport_cost2 = abs(i3-i1) + abs(j3-j1) + abs(i4-i2) + abs(j4-j2);
              mcost = max(mcost, min(normal_cost, min(teleport_cost1, teleport_cost2)));
            }
          }
          res = min(res, mcost);
        }
      }
      return res;
    }
};