-
#17837 새로운 게임 2Code/BOJ 2020. 2. 9. 20:01728x90반응형
출처: https://www.acmicpc.net/problem/17837
17837번: 새로운 게임 2
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽
www.acmicpc.net
A번 말이 이동하려는 칸이
- 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
- A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
- 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
- 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
- A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
- A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
- 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
- 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
실수했던 부분은 파란색을 밟고 그 다음 위치가 원래위치일 경우 그 자리가 빨간색일때 순서를 바꿔주면 안되는데 바꿔 계속 틀렸다. 문제 설명이 조금 부족한 감이 없지 않아 있다.
소스코드
A번 말이 이동하려는 칸이
- 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
- A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
- 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
- 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
- A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
- A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
- 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
- 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters// #17837 새로운 게임 2 #include <iostream> #include <deque> #include <cstring> #include <algorithm> using namespace std; int dir[5][2] = { {0,0}, { 0,1 }, { 0,-1 }, { -1,0 }, { 1,0 } }; int map[13][13];//0은 흰,1은 빨,2는 파 int n, k;// 맵 사이즈, 말의 수 typedef struct info { int num;//드론 넘버 int x, y, d; }; typedef struct info2 { int num, d; }; info init_dron[11]; deque <info2> dron[13][13]; void move_dron(int dron_num,int x,int y,int nx,int ny,int nd,int keep_idx,int dron_size,int red) { //cout << "x " << x << " y " << y << " nx " << nx << " ny " << ny << " nd " << nd <<" keepidx "<<keep_idx<<" red "<<red<< endl; if (x == nx && y == ny) { init_dron[dron_num].d = nd; dron[nx][ny][keep_idx].d = nd; return; } init_dron[dron_num] = { dron_num,nx,ny,nd }; dron[x][y][keep_idx] = { dron_num,nd }; if (red==0) { for (int i = keep_idx; i < dron_size; i++) { int num = dron[x][y][i].num, d = dron[x][y][i].d; init_dron[num].x = nx, init_dron[num].y = ny; dron[nx][ny].push_back({ num,d }); } for (int i = keep_idx; i < dron_size; i++) { dron[x][y].pop_back(); } } else if(red==1) { for (int i = dron_size-1; i >= keep_idx; i--) { int num = dron[x][y][i].num, d = dron[x][y][i].d; //cout << "red stack num " << num << endl; dron[x][y].pop_back(); init_dron[num].x = nx, init_dron[num].y = ny; dron[nx][ny].push_back({ num,d }); } } //cout << endl; } int simul() { //맨 처음 드론 넣기 for (int i = 1; i <= k; i++) { int x = init_dron[i].x, y = init_dron[i].y, num = init_dron[i].num, d = init_dron[i].d; dron[x][y].push_back({ num,d }); } int TIME = 1; while (TIME <= 1000) { for (int dron_num = 1; dron_num <= k; dron_num++) { int x = init_dron[dron_num].x, y = init_dron[dron_num].y, d = init_dron[dron_num].d; if (dron[x][y].size() >= 4)return TIME; int keep_idx;//해당 인덱스부터 마지막까지 데리고 다님 int dron_size = dron[x][y].size(); int nx = x + dir[d][0], ny = y + dir[d][1], nd = d; for (int i = 0; i < dron_size; i++) { if (dron[x][y][i].num == dron_num) { keep_idx = i; break; } } //파란색인 경우 if (nx <= 0 || ny <= 0 || nx > n || ny > n || map[nx][ny] == 2) { if (nd % 2 == 0) { if (nd == 2)nd = 1; else nd = 3; } else nd += 1; nx = x + dir[nd][0], ny = y + dir[nd][1]; if (nx <= 0 || ny <= 0 || nx > n || ny > n || map[nx][ny] == 2) { nx = x, ny = y; } } //흰색인 경우 if (map[nx][ny] == 0) { move_dron(dron_num,x, y, nx, ny, nd, keep_idx, dron_size,0); } //빨간색인 경우 else if (map[nx][ny] == 1) { move_dron(dron_num,x, y, nx, ny, nd, keep_idx, dron_size, 1); } if (dron[nx][ny].size() >= 4)return TIME; } TIME++; } return -1; } void Input() { cin >> n >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> map[i][j]; } } int x, y, d; for (int i = 1; i <= k; i++) { cin >> x >> y >> d; init_dron[i] = { i,x,y,d }; } } int main() { Input(); cout << simul() << endl; } 728x90반응형'Code > BOJ' 카테고리의 다른 글
순열, 조합 뽑기 연습 N과 M (1)~(12) (0) 2020.02.09 #17135 캐슬 디펜스 (0) 2020.02.09 #14500 테트로미노 (0) 2020.01.05 #17406 배열 돌리기 4 (0) 2020.01.05 #2718 타일 채우기 (0) 2020.01.05 - 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.