84分求助QAQ,,,
查看原帖
84分求助QAQ,,,
953238
lucas114514楼主2024/3/9 21:19
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int fx[4] = {-1, 0, 1, 0};
int fy[4] = {0, 1, 0, -1};
int N, M;
char map[17000], visit[17000];
struct point {
    int x, y, d;
};
int gx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int gy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
bool check(int x, int y, int x2, int y2) {
    if (x == x2 || y == y2 || abs(x - x2) == abs(y - y2)) {
        for (int i = 0; i < 8; i++) {
            int tox = x, toy = y;
            while (tox >= 0 && tox < N && toy >= 0 && toy < M) {
                tox += gx[i];
                toy += gy[i];
                if (visit[toy+tox*M] == 'X') break;
                else if (tox == x2 && toy == y2) return true;
            }
        }
        return false;
    }
    else return false;
}
int bfs(int x1, int y1, int x2, int y2) {
    queue<point>q;
    point start{x1, y1, 0};
    q.push(start);
    if (x1 == x2 && y1 == y2) return 0;
    if (check(x1, y1, x2, y2)) return 0;
    while(!q.empty()) {
        point temp = q.front();
        q.pop();
        if (check(temp.x, temp.y, x2, y2)) return temp.d;
        for (int i = 0; i < 4; i++) {
            int tox = temp.x + fx[i], toy = temp.y + fy[i];
            // if (check(tox, toy, x2, y2)) {
            //     return temp.d + 1;
            // }
            if (tox >= 0 && tox < N && toy >= 0 && toy < M && visit[toy+tox*M] == 'O') {
                visit[toy+tox*M] = 'X';
                point to{tox, toy, temp.d + 1};
                q.push(to);
            }
        }
    }

    return -1;
}
int main() {
    cin >> N >> M;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) cin >> map[c+r*M];
    }
    int x1, y1, x2, y2;
    scanf("%d %d %d %d", &x2, &y2, &x1, &y1);
    while(!(x1 == 0 && x2 == 0 && y1 == 0 && y2 == 0)) {
        x2--; y2--; x1--; y1--;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) visit[c+r*M] = map[c+r*M];
        }
        int ans = bfs(x1, y1, x2, y2);
        if (ans != -1) cout << ans << endl;
        else cout << "Poor Harry" << endl;
        scanf("%d %d %d %d", &x2, &y2, &x1, &y1);
    }
    return 0;
}
2024/3/9 21:19
加载中...