社区讨论

80分求助

P2199最后的迷宫参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lowy61o1
此快照首次捕获于
2023/11/13 21:35
2 年前
此快照最后确认于
2023/11/14 07:29
2 年前
查看原帖
CPP
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
struct node {
    int x, y, t;
    node() {
    }
    node(const int &xx, const int &yy, const int &tt) { 
        x = xx, y = yy, t = tt;
    }
};
bool map[5005][5005]; 
bool vis[5005][5005]; 
int n, m, walk[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
void seach(const int &x, const int &y, const int &ex, const int &ey);
bool pd(const int &x, const int &y, const int &ex, const int &ey); 

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char temp;
            cin >> temp;
            map[i][j] = ((temp == 'X') ? false : true); 
        }
    }
    int x, y, xx, yy;
    while (scanf("%d%d%d%d", &x, &y, &xx, &yy)) {
        memset(vis, 0, sizeof(vis)); 
        if (x == 0 && y == 0 && xx == 0 && yy == 0) {
            break;
        }
        if (!map[x][y]) {
            printf("Poor Harry\n");
            continue;
        }
        seach(xx, yy, x, y);
    }
    return 0;
}

void seach(const int &x, const int &y, const int &ex, const int &ey) {
    queue<node> q;
    q.push(node(x, y, 0));
    vis[x][y] = true;
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        if (pd(now.x, now.y, ex, ey)) { 
            printf("%d\n", now.t);
            return;
        }
        for (int i = 0; i < 4; ++i) { 
            int nx = now.x + walk[i][0];
            int ny = now.y + walk[i][1];
            if (map[nx][ny] && !vis[nx][ny]) { 
                vis[nx][ny] = true;
                q.push(node(nx, ny, now.t + 1)); 
            }
        }
    }
    printf("Poor Harry\n"); 
}
bool pd(const int &x, const int &y, const int &ex, const int &ey) {
    for (int i = 0; i < 8; ++i) {
        int nx = x, ny = y;
        while (map[nx][ny]) { 
            if (nx == ex && ny == ey) {
                return true;
            }
            nx += walk[i][0], ny += walk[i][1]; 
        }
    }
    return false; 
}

回复

2 条回复,欢迎继续交流。

正在加载回复...