제출 #1346769

#제출 시각아이디문제언어결과실행 시간메모리
1346769mxhrvsSuperpiece (EGOI22_superpiece)C++20
0 / 100
1 ms412 KiB
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>

using namespace std;

struct Node {
    int r, c, dist;
};

const int OFFSET = 20;
const int SIZE = 45; 

int solve() {
    string pieces;
    cin >> pieces;
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if (a == c && b == d) return 0;

    queue<Node> q;
    q.push({a, b, 0});

    bool visited[SIZE][SIZE] = {false};
    visited[a + OFFSET][b + OFFSET] = true;

    while (!q.empty()) {
        Node curr = q.front();
        q.pop();

        if (curr.r == c && curr.c == d) return curr.dist;

        vector<pair<int, int>> next_moves;

        if (pieces.find('P') != string::npos) {
            next_moves.push_back({curr.r + 1, curr.c});
        }

        if (pieces.find('K') != string::npos) {
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 && dc == 0) continue;
                    next_moves.push_back({curr.r + dr, curr.c + dc});
                }
            }
        }

        if (pieces.find('N') != string::npos) {
            int dr[] = {2, 2, -2, -2, 1, 1, -1, -1};
            int dc[] = {1, -1, 1, -1, 2, -2, 2, -2};
            for (int i = 0; i < 8; i++) {
                next_moves.push_back({curr.r + dr[i], curr.c + dc[i]});
            }
        }

        if (pieces.find('R') != string::npos || pieces.find('Q') != string::npos) {
            int dr[] = {0, 0, 1, -1};
            int dc[] = {1, -1, 0, 0};
            for (int i = 0; i < 4; i++) {
                for (int k = 1; k < SIZE; k++) {
                    int nr = curr.r + dr[i] * k;
                    int nc = curr.c + dc[i] * k;
                    if (nr + OFFSET >= 0 && nr + OFFSET < SIZE && nc + OFFSET >= 0 && nc + OFFSET < SIZE) {
                        next_moves.push_back({nr, nc});
                    } else break;
                }
            }
        }

        if (pieces.find('B') != string::npos || pieces.find('Q') != string::npos) {
            int dr[] = {1, 1, -1, -1};
            int dc[] = {1, -1, 1, -1};
            for (int i = 0; i < 4; i++) {
                for (int k = 1; k < SIZE; k++) {
                    int nr = curr.r + dr[i] * k;
                    int nc = curr.c + dc[i] * k;
                    if (nr + OFFSET >= 0 && nr + OFFSET < SIZE && nc + OFFSET >= 0 && nc + OFFSET < SIZE) {
                        next_moves.push_back({nr, nc});
                    } else break;
                }
            }
        }

        for (auto& m : next_moves) {
            int nr = m.first, nc = m.second;
            if (nr + OFFSET >= 0 && nr + OFFSET < SIZE && nc + OFFSET >= 0 && nc + OFFSET < SIZE) {
                if (!visited[nr + OFFSET][nc + OFFSET]) {
                    visited[nr + OFFSET][nc + OFFSET] = true;
                    q.push({nr, nc, curr.dist + 1});
                }
            }
        }
    }

    return -1;
}

int main() {
    int q;
    if (!(cin >> q)) return 0;
    while (q--) {
        cout << solve() << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...