[백준 25558] 내비게이션 (C#, C++) - soo:bak

문제 링크

25558번 - 내비게이션

설명

각 내비게이션이 안내하는 중간 지점을 순서대로 거칠 때의 총 맨해튼 거리를 계산해, 가장 짧은 데이터를 고르는 문제입니다.

접근법

각 내비게이션마다 시작점→첫 점→…→마지막 점→도착점의 맨해튼 거리 합을 구합니다.
총합이 가장 작은 내비게이션의 번호를 출력합니다.

---

Code

C#

using System;

class Program {
  static long Dist(long ax, long ay, long bx, long by) {
    var dx = ax - bx;
    if (dx < 0) dx = -dx;
    var dy = ay - by;
    if (dy < 0) dy = -dy;
    return dx + dy;
  }

  static void Main() {
    var parts = Console.In.ReadToEnd().Split();
    var idx = 0;
    var n = int.Parse(parts[idx++]);
    var sx = long.Parse(parts[idx++]);
    var sy = long.Parse(parts[idx++]);
    var ex = long.Parse(parts[idx++]);
    var ey = long.Parse(parts[idx++]);

    long best = long.MaxValue;
    var bestIdx = 1;
    for (var i = 1; i <= n; i++) {
      var m = int.Parse(parts[idx++]);
      var px = sx;
      var py = sy;
      long sum = 0;
      for (var j = 0; j < m; j++) {
        var x = long.Parse(parts[idx++]);
        var y = long.Parse(parts[idx++]);
        sum += Dist(px, py, x, y);
        px = x;
        py = y;
      }
      sum += Dist(px, py, ex, ey);

      if (sum < best) {
        best = sum;
        bestIdx = i;
      }
    }

    Console.WriteLine(bestIdx);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dist(ll ax, ll ay, ll bx, ll by) {
  ll dx = ax - bx;
  if (dx < 0) dx = -dx;
  ll dy = ay - by;
  if (dy < 0) dy = -dy;
  return dx + dy;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  ll sx, sy, ex, ey;
  cin >> sx >> sy >> ex >> ey;

  ll best = (1LL << 62);
  int bestIdx = 1;
  for (int i = 1; i <= n; i++) {
    int m; cin >> m;
    ll px = sx, py = sy;
    ll sum = 0;
    for (int j = 0; j < m; j++) {
      ll x, y; cin >> x >> y;
      sum += dist(px, py, x, y);
      px = x;
      py = y;
    }
    sum += dist(px, py, ex, ey);

    if (sum < best) {
      best = sum;
      bestIdx = i;
    }
  }

  cout << bestIdx << "\n";

  return 0;
}