[BOJ] 4042 : Vampires!

https://www.acmicpc.net/problem/4042

BOJ - Vampires!

문제 유형: 구현

문제 난이도: Silver I

 

 

문제

The big media gimmick these days seems to be vampires. Vampire movies, vampire television shows, vampire books, vampire dolls, vampire cereal, vampire lipstick, vampire bunnies – kids and teenagers and even some adults spend lots of time and money on vampire-related stuff. Surprisingly, nowadays vampires are often the good guys. Obviously, the ACM Programming Contest had better have a vampire problem in order to be considered culturally relevant.

As eveyone knows, vampires are allergic to garlic, sunlight, crosses, wooden stakes, and the Internal Revenue Service. But curiously they spend a good part of their time smashing mirrors. Why? Well, mirrors can’t hurt vampires physically, but it’s embarrassing to be unable to cast a reflection. Mirrors hurt vampire’s feelings. This problem is about trying to help them avoid mirrors.

In a room full of vampires and ordinary mortals there are a number of mirrors. Each mirror has one of four orientations – north, south, east, or west (the orientation indicates which side of the mirror reflects). A vampire is in danger of embarrassment if he or she is in a direct horizontal or vertical line with the reflecting side of a mirror, unless there are intervening objects (mortals or other mirrors). For example, in the following room layout

vampire V2 is exposed to a south-facing mirror and both vampires V1 and V2 are exposed to a west-facing mirror (note that a vampire can’t protect another vampire from embarrassment since neither one casts a reflection.) Your job is to notify each vampire of the directions in which there is danger of experiencing ENR (embarrassing non-reflectivity).

 

(서론은 생략)

뱀파이어는 거울로부터 쬐면 위험하다. 각 뱀파이어가 어느 방향으로부터 위험한지 구하시오.

단, 중간에 무언가가 있으면 거울을 막아줘서 괜찮다.(단, 뱀파이어 제외)

 

입력

각 테스트케이스틑 v o m으로 주어집니다.

각각 뱀파이어의 수, 일반인의 수, 거울의 수입니다.

각 v개의 라인은 각 뱀파이어의 x, y좌표의 쌍이 순서대로 주어집니다.

그 뒤 o개의 라인은 각 일반인들의 x, y좌표쌍이 주어집니다.

그 뒤 m개의 라인으로, (방향, 시작x좌표, 시작 y좌표, 종료 x좌표, 종료 y좌표)의 꼴로 거울 정보가 주어집니다.

방향은 N, S, E, W로, 한 줄로 나오는것이 보장됩니다. 이 방향은 거울이 보고 있는 방향을 뜻합니다.

 

칸이 중복되지 않는 것이 보장됩니다.

 

v o m이 0 0 0으로 주어질 시, 종료하시오.

 

출력

각 테스트케이스당, 위험에 처한 뱀파이어가 어디 방향으로부터 위험한지 출력하시오.

출력 순서는 

vampire <뱀파이어번호> <east, north, south, west>순서로 위험한 방향을 출력해야 합니다.

아무도 없는 경우, none을 반환합니다.

 

(자세한 사항은 문제 홈페이지의 예제 참고)

 

풀이

해시맵을 이용할 것이다.

row[y]에는 그 y좌표에 있는 개체들을 저장한다.

{x좌표, 개체번호}로 저장한다.

개체 번호는 다음과 같이 정의했다:

0: 뱀파이어

1: 일반 사람

2: 서쪽을 보는 거울

3: 남쪽을 보는 거울

4: 북쪽을 보는 거울

5: 동쪽을 보는 거울

 

col[x]에도 ={y좌표, 개체번호}로 저장한다.

모든 뱀파이어와 사람, 거울에 대해서 저장해주면 된다.

거울은 범위에 해당하는 모든 칸을 하나하나 추가해준다.

 

각 뱀파이어에 대해서, 동-북-남-서의 방향을 점검할 것이다.

1)동쪽방향 위협 체크: 

현재 같은 y좌표에서 자신보다 x좌표가 더 큰 서쪽을 바라보는 거울을 찾는다.

  만약 있다면, 뱀파이어의 x좌표 < 중간 방해물의 x좌표 < 거울의 x좌표를 만족하는 중간 요소가 있는지 찾는다.

  이 중간 요소는 서쪽을 바라보는 거울이면 안되고, 또, 뱀파이어면 안된다.

    만약 중간 방해물이 있다면, 안전하다.
  만약 현재 같은 y좌표에서 만족하는 중간 방해물을 찾지 못했다면, 동쪽으로부터 위협이 있는 것이다. 더 이상의 탐색을 멈춘다.

 

2)북쪽방향 위협 체크:

현재 같은 x좌표에서 자신보다 y좌표가 더 큰 남쪽을 바라보는 거울을 찾는다.

  만약 있다면, 뱀파이어의 y좌표 < 중간 방해물의 y좌표 < 거울의 y좌표를 만족하는 중간 요소가 있는지 찾는다.

  이 중간 요소는 남쪽을 바라보는 거울이면 안되고, 또, 뱀파이어면 안된다.

    만약 중간 방해물이 있다면, 안전하다.
  만약 현재 같은 x좌표에서 만족하는 중간 방해물을 찾지 못했다면, 북쪽으로부터 위협이 있는 것이다. 더 이상의 탐색을 멈춘다.

 

3)남쪽방향 위협 체크:

 2번의 반대로 하면 된다.

 

4)서쪽방향 위협 체크:

1번의 반대대로 하면 된다.

 

하나 이상이라도 위협이 있다면, 그 뱀파이어에 대해 위협 정보를 출력한다.

 

만약 모든 뱀파이어가 안전하다면, none을 반환한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

// 0: vampire
// 1: ordinary
// 2: west mirror
// 3: south mirror
// 4: north mirror
// 5: east mirror

void solve(int c, int v, int o, int m) {
  vector<pair<int, int>> vampires;
  unordered_map<int, vector<pair<int, int>>> row;
  unordered_map<int, vector<pair<int, int>>> col;

  char dir;
  int x0, y0, x1, y1;
  for (int i = 0; i < v; ++i) {
    cin >> x0 >> y0;
    vampires.push_back({x0, y0});
    row[y0].push_back({x0, 0});
    col[x0].push_back({y0, 0});
  }

  for (int i = 0; i < o; ++i) {
    cin >> x0 >> y0;
    row[y0].push_back({x0, 1});
    col[x0].push_back({y0, 1});
  }

  for (int i = 0; i < m; ++i) {
    int dircode;
    cin >> dir >> x0 >> y0 >> x1 >> y1;
    switch (dir) {
    case 'W':
      dircode = 2;
      break;
    case 'S':
      dircode = 3;
      break;
    case 'N':
      dircode = 4;
      break;
    case 'E':
      dircode = 5;
    }

    if (dircode == 3 || dircode == 4) {
      int from = min(x0, x1);
      int to = max(x0, x1);
      int y = y0;

      for (int j = from; j <= to; ++j) {
        col[j].push_back({y, dircode});
        row[y].push_back({j, dircode});
      }
    } else {
      int from = min(y0, y1);
      int to = max(y0, y1);
      int x = x0;

      for (int j = from; j <= to; ++j) {
        col[x].push_back({j, dircode});
        row[j].push_back({x, dircode});
      }
    }
  }

  bool flag = true;
  cout << "Case " << c << ":\n";
  for (int i = 0; i < v; ++i) {
    string status = "";
    int x = vampires[i].first;
    int y = vampires[i].second;

    // check east.
    for (const auto &element : row[y]) {
      if (element.second == 2 && element.first > x) {
        bool safe = false;
        for (const auto &shield : row[y]) {
          if (shield.second != 2 && shield.second != 0 && shield.first > x &&
              shield.first < element.first) {
            safe = true;
            break;
          }
        }
        if (!safe) {
          status += " east";
          break;
        }
      }
    }

    // check north
    for (const auto &element : col[x]) {
      if (element.second == 3 && element.first > y) {
        bool safe = false;
        for (const auto &shield : col[x]) {
          if (shield.second != 3 && shield.second != 0 && shield.first > y &&
              shield.first < element.first) {
            safe = true;
            break;
          }
        }
        if (!safe) {
          status += " north";
          break;
        }
      }
    }

    // check south
    for (const auto &element : col[x]) {
      if (element.second == 4 && element.first < y) {
        bool safe = false;
        for (const auto &shield : col[x]) {
          if (shield.second != 4 && shield.second != 0 && shield.first < y &&
              shield.first > element.first) {
            safe = true;
            break;
          }
        }
        if (!safe) {
          status += " south";
          break;
        }
      }
    }

    // check west.
    for (const auto &element : row[y]) {
      if (element.second == 5 && element.first < x) {
        bool safe = false;
        for (const auto &shield : row[y]) {
          if (shield.second != 5 && shield.second != 0 && shield.first < x &&
              shield.first > element.first) {
            safe = true;
            break;
          }
        }
        if (!safe) {
          status += " west";
          break;
        }
      }
    }

    if (status.size() != 0) {
      cout << "vampire " << i + 1 << status << "\n";
      flag = false;
    }
  }
  if (flag) {
    cout << "none\n";
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int c = 1;
  int v, o, m;
  while (true) {
    cin >> v >> o >> m;
    if (v == 0 && o == 0 && m == 0) {
      break;
    }
    solve(c, v, o, m);
    c++;
  }
  return 0;
}