ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 13460번 C++ 코드
    백준 2020. 1. 15. 00:53
    #include <iostream>
    #include <climits>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #include <map>
    #include <list>
    #include <stack>
    #include <set>
    
    using namespace std;
    
    
    using pii = pair<int, int>;
    using tiiii = tuple<int, int, int, int, int>;
    int n, m;
    
    bool isVisited[10][10][10][10];
    
    int dp[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    char buffer[10][10];
    bool hasRoute = false;
    int answer = INT_MAX;
    queue<tiiii> q;
    
    
    struct Element {
        int redX;
        int redY;
        int blueX;
        int blueY;
    };
    
    bool isInside(int x, int y) {
        return 0 < x && x < m-1 && 0 < y && y < n-1;
    }
    
    void printState(
            int turn,
            int redX, int redY, int blueX, int blueY) {
    //    cout << "Turn\t" << turn << '\n';
    //    for (auto y=0; y<n; y++) {
    //        for (auto x = 0; x < m; x++) {
    //            if ( (x == redX) && (y == redY) ) {
    //                cout << 'R';
    //                continue;
    //            }
    //
    //            if ( (x == blueX) && (y == blueY) ) {
    //                cout << 'B';
    //                continue;
    //            }
    //            cout << buffer[x][y];
    //        }
    //        cout << '\n';
    //    }
    }
    
    void move(int &x, int &y, int directionIndex) {
        auto d = dp[directionIndex];
        while (true) {
    
            if (buffer[x][y] == 'O') {
                return;
            }
    
            auto nextX = x + d[0];
            auto nextY = y + d[1];
    
    
            if (buffer[nextX][nextY] == '#') {
                return;
            }
            x = nextX;
            y = nextY;
        }
    }
    
    void turn(int numberOfTurn, int redX, int redY, int blueX, int blueY, int directionIndex);
    void universalTurn(int numberOfTurn, int redX, int redY, int blueX, int blueY) {
       if (numberOfTurn >= 10) {
            return;
        }
    
        for (auto i=0; i<4; i++) {
            turn(numberOfTurn, redX, redY, blueX, blueY, i);
        }
    
    
    }
    
    void turn(int numberOfTurn, int redX, int redY, int blueX, int blueY, int directionIndex) {
        int previousBlueX = blueX;
        int previousBlueY = blueY;
        int previousRedX = redX;
        int previousRedY = redY;
        move(blueX, blueY, directionIndex);
        move(redX, redY, directionIndex);
        if (buffer[blueX][blueY] == 'O') {
            return;
        }
        if (buffer[redX][redY] == 'O') {
    //        cout << numberOfTurn << '\n';
            hasRoute = true;
            answer = min(answer, numberOfTurn);
            return;
        }
    
        if ( (redX == blueX) && (redY == blueY)) {
    
            auto d = dp[directionIndex];
    
            bool shouldMoveRed = true;
    
            if (directionIndex == 0) {
                if (previousRedX < previousBlueX) {
                    shouldMoveRed = true;
                } else {
                    shouldMoveRed = false;
                }
            } else if (directionIndex == 1) {
                if (previousRedY < previousBlueY) {
                    shouldMoveRed = true;
                } else {
                    shouldMoveRed = false;
                }
            } else if (directionIndex == 2) {
                if (previousRedX < previousBlueX) {
                    shouldMoveRed = false;
                } else {
                    shouldMoveRed = true;
                }
            } else {
                if (previousRedY < previousBlueY) {
                    shouldMoveRed = false;
                } else {
                    shouldMoveRed = true;
                }
            }
    
            if (shouldMoveRed) {
                redX -= d[0];
                redY -= d[1];
            } else {
                blueX -= d[0];
                blueY -= d[1];
            }
    
        }
    
    
    //    cout << redX << '\t' << redY << '\t' << blueX << '\t' << blueY << '\n';
    
        if (isVisited[redX][redY][blueX][blueY]) {
            return;
        }
        printState(numberOfTurn, redX, redY, blueX, blueY);
    
        isVisited[redX][redY][blueX][blueY] = true;
    
        q.push({numberOfTurn+1, redX, redY, blueX, blueY});
    }
    
    
    
    int main() {
        ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
        cin >> n >> m;
    
        int redX, redY, blueX, blueY;
    
    
        for (auto y=0; y<n; y++) {
            for (auto x=0; x<m; x++) {
                char temp;
                cin >> temp;
                if (temp == 'R') {
                    redX = x;
                    redY = y;
                    buffer[x][y] = '.';
                } else if (temp == 'B') {
                    blueX = x;
                    blueY = y;
                    buffer[x][y] = '.';
                } else {
                    buffer[x][y] = temp;
                }
    
            }
        }
    
    
    //    cout << redX << redY;
    ;
        isVisited[redX][redY][blueX][blueY] = true;
    
        q.push({0, redX, redY, blueX, blueY});
    
    
    
        while (!q.empty()) {
            auto value = q.front();
            q.pop();
            universalTurn(get<0>(value), get<1>(value), get<2>(value), get<3>(value), get<4>(value));
        }
        if (hasRoute) {
            cout << answer + 1;
        } else {
            cout << -1;
        }
        return 0;
    }

    '백준' 카테고리의 다른 글

    백준 1604번 python 3 풀이  (0) 2020.01.24
    백준 1797번 C++ 풀이  (0) 2020.01.19
    백준 13460번 C++ 코드  (0) 2020.01.15
    백준 17370번 풀이  (0) 2019.12.03
    백준 16681번 풀이  (0) 2019.12.01
    PS(알고리즘) 오픈 톡방 신입부원 대 모집!!  (0) 2019.12.01

    댓글 0

Designed by Tistory.