새로운 게임2

 

*맵의 가장자리를 모두 2로 설정해서 범위를 벗어나는 경우에도 파란색 칸에 간 것과 같이 처리했음 

*vector를 이차원 배열로 사용해서 reverse, insert, clear로 쉽게 구현을 했다.

*이 문제에서 가장 핵심적으로 고려해야 할 점은 파란색 칸을 만나서 방향을 바꿔서 나오는 경우에 다음에 만나는 칸의 색을 고려해야 한다. 

-빨간색이면 순서를 뒤집어서 다시 저장을 해야할 것이고, 파란색이면 방향만 바뀐채로 저장이 될 것이다.

#include <iostream> #include <vector> #include <queue> #include <cstring> #include <algorithm> using namespace std; int n, k; bool flag = 0; int map[14][14]; vector<int> chase[14][14]; typedef pair<int, int> pp; typedef pair<int, pp> ipp; int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0}; typedef struct Horse { int x, y, d; Horse(){}; Horse(int _x, int _y, int _d) : x(_x), y(_y), d(_d){}; }; Horse horses[11]; //0 - white, 1 - red 2 - blue bool checkRange(int x, int y) { if (x < 1 || x > n || y < 1 || y > n) return false; return true; } void moveHorse(int idx) { //0 - white, 1 - red 2 - blue //이 말의 이동 방향에 따라 움직인다. Horse now = horses[idx]; int x = now.x; int y = now.y; int d = now.d; //현재 말 정보 꺼냄 //chase에서 처음에 있는 인덱스일수록 바닥에 가깝다. //모두 꺼내면 안된다. vector<int> tmp = chase[x][y]; vector<int> tmp2; for (int i = 0; i < tmp.size(); i++) { if (tmp[i] == idx) { tmp2.insert(tmp2.begin(), tmp.begin() + i, tmp.end()); chase[x][y].clear(); if (i != 0) { chase[x][y].insert(chase[x][y].begin(), tmp.begin(), tmp.begin() + i); } break; } } int nx = x + dx[d]; int ny = y + dy[d]; if (!checkRange(nx, ny) || map[nx][ny] == 2) { //벽이나 파란칸을 만났을 때 //방향을 반대로 하고 한 번 더 확인 d = d < 2 ? 1 - d : 5 - d; nx = x + dx[d]; ny = y + dy[d]; if (!checkRange(nx, ny) || map[nx][ny] == 2) { horses[idx].d = d; chase[x][y].insert(chase[x][y].end(), tmp2.begin(), tmp2.end()); if (chase[x][y].size() >= 4) flag = 1; return; } } if (map[nx][ny] == 0) { //그 칸으로 이동 horses[idx].d = d; //방향이 반대로 바뀌었을수도 있으니까 for (int i = 0; i < tmp2.size(); i++) { horses[tmp2[i]].x = nx; horses[tmp2[i]].y = ny; } chase[nx][ny].insert(chase[nx][ny].end(), tmp2.begin(), tmp2.end()); if (chase[nx][ny].size() >= 4) flag = 1; return; } if (map[nx][ny] == 1) { //red horses[idx].d = d; reverse(tmp2.begin(), tmp2.end()); for (int i = 0; i < tmp2.size(); i++) { horses[tmp2[i]].x = nx; horses[tmp2[i]].y = ny; } chase[nx][ny].insert(chase[nx][ny].end(), tmp2.begin(), tmp2.end()); if (chase[nx][ny].size() >= 4) flag = 1; return; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> map[i][j]; } } for (int i = 0; i < k; i++) { int x, y, d; cin >> x >> y >> d; horses[i] = Horse(x, y, d - 1); chase[x][y].push_back(i); //i번째 말이 이 칸에 있음을 표시 } int cnt = 0; bool stop = true; while (stop) { ++cnt; if (cnt > 1000) { cnt = -1; break; } //말을 움직인다. for (int i = 0; i < k; i++) { moveHorse(i); if (flag) { stop = false; break; } } } cout << cnt << '\n'; return 0; }