시뮬레이션과 구현
상어 초등학교 (vector 정렬)
4gats
2023. 9. 15. 13:26
https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
빡 구현 문제다.
|r1 - r2| + |c1 - c2| = 1
이건 그냥 상, 하, 좌, 우
그냥 1,2,3 조건을 순서대로 따라가면 된다.
처음에는 함수를 3개 만들었다. 잘 되지 않았다..
한 번에 할 수 있었다!
struct POSITION
{
int x;
int y;
int near_empty;
int near_friend;
};
구조체를 선언하고 vector<POSITION> Pos;
를 선언후 cmp 함수를 이용해 sort를 하고
sort(Pos.begin(), Pos.end(), cmp);
cmp 함수를 설정해주어 정렬 시키면 되겠다!
|
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int n;
int ans = 0;
int map[25][25];
struct STUDENT
{
int num;
int suki[4];
};
struct POSITION
{
int x;
int y;
int near_empty;
int near_friend;
};
vector<STUDENT> student;
STUDENT student_arr[25 * 25];
bool cmp(POSITION A, POSITION B)
{
if (A.near_friend == B.near_friend)
{
if (A.near_empty == B.near_empty)
{
if (A.x == B.x)
{
return A.y < B.y;
}
return A.x < B.x;
}
return A.near_empty > B.near_empty;
}
return A.near_friend > B.near_friend;
}
void set_position()
{
for (int i = 0; i < student.size(); i++)
{
vector<POSITION> Pos;
int student_num = student[i].num;
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
{
if (map[x][y] != 0)
continue;
int near_friend = 0;
int near_empty = 0;
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n)
{
if (map[nx][ny] == 0)
near_empty++;
else
{
for (int j = 0; j < 4; j++)
{
int friend_num = student[i].suki[j];
if (map[nx][ny] == friend_num)
{
near_friend++;
break;
}
}
}
}
Pos.push_back({ x, y, near_empty, near_friend });
}
}
}
sort(Pos.begin(), Pos.end(), cmp);
int Pos_x = Pos[0].x;
int Pos_y = Pos[0].y;
map[Pos_x][Pos_y] = student_num;
}
}
void calculate_satisfy()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int student_num = map[i][j];
int cnt = 0;
for (int k = 0; k < 4; k++)
{
int nx = i + dx[k];
int ny = j + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n)
{
for (int l = 0; l < 4; l++)
{
int friend_num = student_arr[student_num].suki[l];
if (map[nx][ny] == friend_num)
{
cnt++;
break;
}
}
}
}
if (cnt == 4)
ans += 1000;
else if (cnt == 3)
ans += 100;
else if (cnt == 2)
ans += 10;
else if (cnt == 1)
ans += 1;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n * n; i++)
{
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
student.push_back({ a, {b, c, d, e} });
student_arr[a].num = a;
student_arr[a].suki[0] = b;
student_arr[a].suki[1] = c;
student_arr[a].suki[2] = d;
student_arr[a].suki[3] = e;
}
set_position();
calculate_satisfy();
cout << ans << '\n';
return 0;
}
|
cs |