[백준 27445] Gorani Command (C#, C++) - soo:bak

문제 링크

27445번 - Gorani Command

설명

격자의 테두리를 따라 이동하며 측정한 맨해튼 거리가 주어질 때, 고라니의 위치를 찾는 문제입니다.

왼쪽 변과 아래쪽 변에서 측정한 거리가 모두 일치하는 위치가 답입니다.

접근법

n, m이 최대 50이므로 모든 칸을 후보로 완전탐색합니다.

각 후보에 대해 왼쪽 변과 아래쪽 변에서의 거리를 계산합니다.

모든 거리가 입력과 일치하면 해당 위치가 정답입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var nm = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
    var n = nm[0];
    var m = nm[1];

    var v = new int[n];
    for (var i = 0; i < n - 1; i++) v[i] = int.Parse(Console.ReadLine()!);
    var bottom = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
    v[n - 1] = bottom[0];

    var ansR = -1;
    var ansC = -1;
    for (var r = 1; r <= n && ansR == -1; r++) {
      for (var c = 1; c <= m; c++) {
        var ok = true;
        for (var i = 1; i <= n; i++) {
          var dist = Math.Abs(r - i) + Math.Abs(c - 1);
          if (dist != v[i - 1]) { ok = false; break; }
        }
        if (!ok) continue;
        for (var j = 1; j <= m; j++) {
          var dist = Math.Abs(r - n) + Math.Abs(c - j);
          if (dist != bottom[j - 1]) { ok = false; break; }
        }
        if (ok) { ansR = r; ansC = c; break; }
      }
    }

    Console.WriteLine($"{ansR} {ansC}");
  }
}

C++

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

typedef vector<int> vi;

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

  int n, m; cin >> n >> m;

  vi v(n);
  for (int i = 0; i < n - 1; i++) cin >> v[i];
  vi bottom(m);
  for (int j = 0; j < m; j++) cin >> bottom[j];
  v[n - 1] = bottom[0];

  int ansR = -1, ansC = -1;
  for (int r = 1; r <= n && ansR == -1; r++) {
    for (int c = 1; c <= m; c++) {
      bool ok = true;
      for (int i = 1; i <= n; i++) {
        int dist = abs(r - i) + abs(c - 1);
        if (dist != v[i - 1]) { ok = false; break; }
      }
      if (!ok) continue;
      for (int j = 1; j <= m; j++) {
        int dist = abs(r - n) + abs(c - j);
        if (dist != bottom[j - 1]) { ok = false; break; }
      }
      if (ok) { ansR = r; ansC = c; break; }
    }
  }

  cout << ansR << " " << ansC << "\n";

  return 0;
}