백준 17837번 : 새로운 게임 2 - 시뮬레이션 Cpp

https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

#include <bits/stdc++.h>

using namespace std;

int N, K;
int chessBoard[13][13];
int horseOnChessBoard[13][13][13];
int horseInfo[11][3];  //x, y, dir
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int cnt = 1;
int ans = -1;

void Input();

vector<int> getHorseToMove(int horseX, int horseY, int i) {
    vector<int> horseToMove;
    int idx = -1;

    for (int j = 0; j < K; j++) {
        if (horseOnChessBoard[horseX][horseY][j] == i) {
            idx = j;
            break;
        }
    }

    for (int j = idx; j < K; j++) {
        if (horseOnChessBoard[horseX][horseY][j] == 0) break;
        horseToMove.push_back(horseOnChessBoard[horseX][horseY][j]);
        horseOnChessBoard[horseX][horseY][j] = 0;
    }

    return horseToMove;
}


void turnDirection(int cur, int &horseDir) {
    if (horseDir == 0) horseDir = 1;
    else if (horseDir == 1) horseDir = 0;
    else if (horseDir == 2) horseDir = 3;
    else if (horseDir == 3) horseDir = 2;
    horseInfo[cur][2] = horseDir;
}


bool checkMove(const vector<int> &horseToMove, int nx, int ny, int top) {
    for (int k = 0; k < horseToMove.size(); k++) {
        int curHorse = horseToMove[k];
        horseOnChessBoard[nx][ny][top++] = curHorse;
        horseInfo[curHorse][0] = nx;
        horseInfo[curHorse][1] = ny;
    }

    if(top>=4){
        ans = cnt;
        return true;
    }
    return false;
}


int getTop(int nx, int ny) {
    int top = 0;
    while (horseOnChessBoard[nx][ny][top] != 0) {
        top++;
    }
    return top;
}

bool moveHorse() {
    for (int i = 1; i <= K; i++) {
        int horseX = horseInfo[i][0];
        int horseY = horseInfo[i][1];
        int horseDir = horseInfo[i][2];
        int nx = horseX + dx[horseDir];
        int ny = horseY + dy[horseDir];

        //move or not move check
        if (nx <= 0 || nx > N || ny <= 0 || ny > N || chessBoard[nx][ny] == 2) {
            turnDirection(i, horseDir);
            nx = horseX + dx[horseDir];
            ny = horseY + dy[horseDir];
            if (nx <= 0 || nx > N || ny <= 0 || ny > N || chessBoard[nx][ny] == 2) continue;
        }
        
        //move
        vector<int> horseToMove = getHorseToMove(horseX, horseY, i);
        if (chessBoard[nx][ny] == 1) reverse(horseToMove.begin(), horseToMove.end());
        int top = getTop(nx, ny);

        if (checkMove(horseToMove, nx, ny, top)) {
            return false;
        }
    }

    return true;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    Input();

    while (moveHorse()) {
        cnt++;

        if (cnt > 1000) {
            cout << -1 << '\n';
            return 0;
        }
    }

    cout << ans << '\n';

    return 0;
}


void Input() {
    cin >> N >> K;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> chessBoard[i][j];

    for (int i = 1; i <= K; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        horseInfo[i][0] = a;
        horseInfo[i][1] = b;
        horseInfo[i][2] = c - 1;
        horseOnChessBoard[a][b][0] = i;
    }
}