https://www.acmicpc.net/problem/17837
17837번: 새로운 게임 2
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하
www.acmicpc.net
처음에는
구조체에 vector를 넣어서
연결리스트로 말 번호를
다 관리하려고 했다.
하지만 그럴 필요가 없다!!
struct chess
{
int row;
int col;
int dir;
};
chess uma[14];
말들의 정보
vector<int> map_state[15][15];
여기에 말들의 상태를 나타내면 된다!
그럼 말들의 이동은 어떻게 구현하는가?
쌓여 있는 상태에서 현재 말의 위치(pos)
구하는 함수 만들어서
|
1
2
3
4
5
6
7
8
9
|
int find_position(int x, int y, int idx)
{
for (int i = 0; i < map_state[x][y].size(); i++)
{
if (map_state[x][y][i] == idx)
return i;
}
}
|
cs |
pos부터 vector의 끝까지 이동을 시키면 된다.
0 이면 그냥 이동
1 이면 size() - 1 부터 이동
<소스 코드>
|
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int dx[] = { 0, 0, 0, -1, 1 };
int dy[] = { 0, 1, -1, 0, 0 };
int n, k;
struct chess
{
int row;
int col;
int dir;
};
chess uma[14];
int map[15][15];
// 중첩된 말들을 표현하는 방법?
vector<int> map_state[15][15];
int change_dir(int num)
{
int dir = uma[num].dir;
if (dir == 1)
return 2;
if (dir == 2)
return 1;
if (dir == 3)
return 4;
if (dir == 4)
return 3;
}
int how_many_delete(int x, int y, int chess_num)
{
/* 해당 말을 옮긴 후, 기존 좌표에서 몇 번 삭제를 해야 하는지 찾는 함수*/
int cnt = 1;
for (int i = map_state[x][y].size() - 1; i >= 0; i--)
{
if (map_state[x][y][i] == chess_num)
break;
cnt++;
}
return cnt;
}
int find_position(int x, int y, int idx)
{
for (int i = 0; i < map_state[x][y].size(); i++)
{
if (map_state[x][y][i] == idx)
return i;
}
}
// 4개 이상인지 체크하는 함수
bool check_state()
{
for (int i = 0; i < k; i++)
{
int x = uma[i].row;
int y = uma[i].col;
if (map_state[x][y].size() >= 4)
return true;
}
return false;
}
void movechess(int x, int y, int nx, int ny, int chess_num, int pos, int how)
{
if (how == 0)
{
for (int i = pos; i < map_state[x][y].size(); i++)
{
map_state[nx][ny].push_back(map_state[x][y][i]);
int idx = map_state[x][y][i];
uma[idx].row = nx;
uma[idx].col = ny;
}
int delete_num = how_many_delete(x, y, chess_num);
for (int i = 0; i < delete_num; i++)
map_state[x][y].pop_back();
}
else if (how == 1)
{
for (int i = map_state[x][y].size() - 1; i >= pos; i--)
{
map_state[nx][ny].push_back(map_state[x][y][i]);
int idx = map_state[x][y][i];
uma[idx].row = nx;
uma[idx].col = ny;
}
int delete_num = how_many_delete(x, y, chess_num);
for (int i = 0; i < delete_num; i++)
map_state[x][y].pop_back();
}
else if (how == 2)
{
int dir = change_dir(chess_num);
uma[chess_num].dir = dir;
int nnx = x + dx[dir];
int nny = y + dy[dir];
if (nnx >= 0 && nny >= 0 && nnx < n && nny < n)
{
if (map[nnx][nny] != 2) movechess(x, y, nnx, nny, chess_num, pos, map[nnx][nny]);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cin >> map[i][j];
}
for (int i = 0; i < k; i++)
{
int x, y, d;
cin >> x >> y >> d;
x--; y--;
uma[i] = { x,y,d };
map_state[x][y].push_back(i);
}
bool flag = false;
int jikan = 0;
while (true)
{
if (jikan > 1000)
break;
for (int i = 0; i < k; i++)
{
int x = uma[i].row;
int y = uma[i].col;
int dir = uma[i].dir;
int nx = x + dx[dir];
int ny = y + dy[dir];
int pos = find_position(x, y, i);
if (nx >= 0 && nx < n && ny >= 0 && ny < n)
movechess(x, y, nx, ny, i, pos, map[nx][ny]);
else
movechess(x, y, nx, ny, i, pos, 2);
if (check_state() == true)
{
cout << jikan + 1 << '\n';
return 0;
}
}
jikan++;
}
cout << -1 << '\n';
return 0;
}
|
cs |
