새로운 게임 (feat. 백준, 17780번)

새로운 게임
https://www.acmicpc.net/problem/17780

17780번: 새로운 게임

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct Horse{
    int x;
    int y;
    int d;
};
int N, K, dx[4], dy[4], arr[13][13];
deque<int> maps[13][13];
vector<Horse> horses;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = dx[1] = 0, dx[2] = -1, dx[3] = 1;
    dy[0] = 1, dy[1] = -1, dy[2] = dy[3] = 0;
    cin >> N >> K;
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j)
            cin >> arr[i][j];
    for(register int k = 1, x, y, d; k <= K; ++k)
        cin >> x >> y >> d, maps[x][y].push_back(k), horses.push_back(Horse{x, y, d - 1});
    bool iend = false;
    register int turn = 0;
    while(!iend && ++turn <= 1000){
        for(auto idx = 0; idx < horses.size(); ++idx){
            register int number = idx + 1, x = horses[idx].x, y = horses[idx].y, d = horses[idx].d;
            if(maps[x][y].back() != number)     // 말이 가장 아래에 있을때만 이동 가능
                continue;
            register int nx = x + dx[d], ny = y + dy[d];
            if(1 <= nx && nx <= N && 1 <= ny && ny <= N){
                if(arr[nx][ny] == 0){   // 이동하려는 곳이 흰색
                    stack<int> tmp_horses;
                    while(1){       // 이동하기전 움직이려는 말과 그 위의 모든 말을 구함(stack)
                        register int t = maps[x][y].front(); maps[x][y].pop_front();
                        tmp_horses.push(t);
                        if(t == number)
                            break;
                    }
                    while(!tmp_horses.empty()){  // 이동하려는 곳으로 모든 말들 옮김
                        register int t = tmp_horses.top();
                        maps[nx][ny].push_front(t), tmp_horses.pop();
                        horses[t - 1].x = nx, horses[t - 1].y = ny;
                    }
                }
                else if(arr[nx][ny] == 1){  // 이동하려는 곳이 빨강
                    queue<int> tmp_horses;
                    while(1){       // 이동하기전 움직이려는 말과 그 위의 모든 말을 구함(queue)
                        register int t = maps[x][y].front(); maps[x][y].pop_front();
                        tmp_horses.push(t);
                        if(t == number)
                            break;
                    }
                    while(!tmp_horses.empty()){  // 이동하려는 곳으로 모든 말들 옮김
                        register int t = tmp_horses.front();
                        maps[nx][ny].push_front(t), tmp_horses.pop();
                        horses[t - 1].x = nx, horses[t - 1].y = ny;
                    }
                }
                else{   // 이동하려는 곳이 파랑
                    // 방향 전환
                    if(d == 0)          d = 1;
                    else if(d == 1)     d = 0;
                    else if(d == 2)     d = 3;
                    else                d = 2;
                    nx = x + dx[d], ny = y + dy[d];
                    horses[idx].d = d;
                    if(1 <= nx && nx <= N && 1 <= ny && ny <= N && arr[nx][ny] != 2)    // 방향 전환후 이동 가능하면 31라인 재수행
                        --idx;
                }
            }
            else{   // 체스판을 벗어나는 경우 파랑과 동일하게
                // 방향 전환
                if(d == 0)          d = 1;
                else if(d == 1)     d = 0;
                else if(d == 2)     d = 3;
                else                d = 2;
                nx = x + dx[d], ny = y + dy[d];
                horses[idx].d = d;
                if(1 <= nx && nx <= N && 1 <= ny && ny <= N && arr[nx][ny] != 2)    // 방향 전환후 이동 가능하면 31라인 재수행
                    --idx;
            }
            // 말이 4개 이상 쌓인곳이 있으면 종료
            for(register int i = 1, j; i <= N; ++i){
                for(j = 1; j <= N; ++j)
                    if(maps[i][j].size() >= 4){
                        iend = true;
                        break;
                    }
                if(iend)
                    break;
            }
            if(iend)
                break;
        }
    }
    if(turn > 1000)
        cout << -1;
    else
        cout << turn;
    return 0;
}
// *&)*@*

 

 

이전 "새로운 게임2" 와 비슷한 문제입니다. 제가 좋아하는 구현 문제입니다.

새로운 게임 2 (feat. 백준, 17837번)

 

차이점이 있다면 이동하려는 말이 가장 아래에 존재할 경우에만 이동 가능합니다.