BOJ17143: 낚시왕

작성일

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

  • 꽤 복잡한 구현인데, 한방에 패스함
  • 생각보다 unordered_set은 훨씬 느림
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;

int R, C, M, ans;
struct Shark {
  int x, y, v, dir, size;
};

Shark* arr[101][101];
unordered_set<Shark*> sharks, remain;

//up, down, right, left
const int dx[5] = {0, -1, 1, 0, 0};
const int dy[5] = {0, 0, 0, 1, -1};
inline bool bound(int x, int y) {
  return x > 0 && y > 0 && x <= R && y <= C;
}

void changeDirection(int& x, int &y, int& d) {
  if(d == 1)      d = 2, x = 1 + (1 - x);
  else if(d == 2) d = 1, x = R - (x - R);
  else if(d == 3) d = 4, y = C - (y - C);
  else if(d == 4) d = 3, y = 1 + (1 - y);
}

void moveShark() {
  memset(arr, 0, sizeof(arr));
  remain.clear();
  for(Shark* shark : sharks) {
    auto& [x,y,v,d,size] = *shark;
    x += dx[d] * v;
    y += dy[d] * v;
    while(!bound(x,y))
      changeDirection(x, y, d);
    Shark* overlap = arr[x][y];
    if(overlap && overlap->size < shark->size) {
      delete overlap;
      remain.erase(overlap);
      remain.insert(shark);
      arr[x][y] = shark;
    } else if(!overlap) {
      remain.insert(shark);
      arr[x][y] = shark;
    }
  }
  sharks = remain;
}

void print() {
  for(int i = 1; i <= R; i++) {
    for(int j = 1; j <= C; j++)
      printf("%d ", arr[i][j] != nullptr);
    printf("\n");
  }
  printf("\n");
}

int main() {
  ios::sync_with_stdio(false);
  cin >> R >> C >> M;
  for(int i = 0; i < M; i++) {
    int r, c, s, d, z;
    cin >> r >> c >> s >> d >> z;
    Shark* shark = new Shark({r,c,s,d,z});
    arr[r][c] = shark;
    sharks.insert(shark);
  }

  for(int y = 1; y <= C; y++) {
    for(int x = 1; x <= R; x++) {
      if(arr[x][y]) {
        ans += arr[x][y]->size;
        delete arr[x][y];
        sharks.erase(arr[x][y]);
        arr[x][y] = 0;
        break;
      }
    }
    moveShark();
  }
  cout << ans;
  return 0;
}