어흥
[백준 17837] 새로운 게임 2 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/17837
1. 주의할 점
- 이동할때 이동하는 말 위의 말은 전부 옮겨야 한다
- 벽면도 파란색과 같은 효과라고 했으므로 배열의 크기를 2씩 늘려서 테두리를 2로 감싸도록 한다 -> 배열 범위 밖 고려 안해도 된다
- Cnt(이동 횟수)가 1000을 넘어가면 -1을 출력한다
- 놓치기 쉬운 부분들은 밑에 빨간색으로 처리했다
2. 구현
- 현재 이동하려는 말 포함해서 위에 있는 말들을 전부 VV 벡터에 담는다
- 이동하려는 칸이 파란색일 경우, 방향을 바꾸고, 반대쪽 칸도 파란색인 경우 Continue한다
- 원래 위치해 있던 칸에서 VV 벡터만큼 Pop_back()을 수행하여 위에 있는 말들을 없앤다
- 이동하려는 칸이 빨간색인 경우 뒤집어서 놓아야하기 때문에 VV 벡터를 Reverse한다
- 이동하려는 칸에 VV 벡터에 있는 값들을 넣고, 이동하려는 칸에 말이 4개 이상 있다면 Cnt를 출력하고 종료한다
- 말들이 전부 한번씩 이동했다면 Cnt++하고 위의 과정을 반복한다
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
int y, x, dir;
};
info tmp;
int arr[14][14], knight, num;
vector<int> chess[14][14]; //해당 칸에 어떤 말들이 있는지 저장
vector<info> v[11];
int dx[5] = { 0,1,-1,0,0 };
int dy[5] = { 0,0,0,-1,1 };
void start() {
int cnt = 1;
bool finish = false;
while (1) {
if (cnt > 1000) {
cout << -1;
break;
}
for (int i = 1; i <= knight; i++) {
int cx = v[i][0].x;
int cy = v[i][0].y;
int cd = v[i][0].dir;
vector<int> vv;
if (chess[cy][cx].size()>0) {
//해당 칸에 있는거 다 넣기
bool found = false;
for (int j = 0; j < chess[cy][cx].size(); j++) {
if (!found) {
if (chess[cy][cx][j] == i) {
found = true;
vv.push_back(chess[cy][cx][j]);
}
}
else
vv.push_back(chess[cy][cx][j]);
}
}
int nx = cx + dx[cd];
int ny = cy + dy[cd];
int val = arr[ny][nx];
//파라색
if (val == 2) {
int nd;
//반대도 확인한다
if (cd == 1) nd = 2;
else if (cd == 2) nd = 1;
else if (cd == 3) nd = 4;
else if (cd == 4) nd = 3;
nx = cx + dx[nd];
ny = cy + dy[nd];
v[i][0].dir = nd;
//뒤가 벽or 파란색
if (arr[ny][nx] == 2)
continue;
else
val = arr[ny][nx];
}
//기존에 있던 말 없애기
for (int k = 0; k < vv.size(); k++)
chess[cy][cx].pop_back();
//빨간색
if (val == 1)
reverse(vv.begin(), vv.end());
for(int k=0;k<vv.size();k++) {
int cidx = vv[k];
chess[ny][nx].push_back(cidx);
v[cidx][0].x = nx;
v[cidx][0].y = ny;
}
if (chess[ny][nx].size() > 3) {
finish = true;
break;
}
}
if (finish) break;
cnt++;
}
if (finish) cout << cnt;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> num >> knight;
for (int i = 0; i < num + 2; i++)
for (int j = 0; j < num + 2; j++)
arr[i][j] = 2;
for (int i = 1; i <= num; i++)
for (int j = 1; j <= num; j++)
cin >> arr[i][j];
int x, y, d;
for (int i = 1; i <= knight; i++) {
cin >> y >> x >> d;
tmp.dir = d;
tmp.x = x;
tmp.y = y;
v[i].push_back(tmp);
chess[y][x].push_back(i);
}
start();
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 17825] 주사위 윷놀이 (C++) (0) | 2020.06.06 |
---|---|
[백준 17822] 원판 돌리기 (C++) (0) | 2020.06.06 |
[백준 17779] 게리맨더링 2 (C++) (0) | 2020.06.06 |
[백준 15661] 링크와 스타트 (C++) (0) | 2020.06.03 |
[백준 2549] 루빅의 사각형 (C++) (0) | 2020.06.02 |
Comments