欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

广搜之逃离迷宫

程序员文章站 2023-12-23 19:58:39
...

广搜之逃离迷宫

广搜之逃离迷宫

#include <cstdio>
#include <queue>

using namespace std;
/*难在预处理子弹位置部分,不熟悉如何处理,需要多加思考多加练习。
*代码依然不是我敲的。
*/
struct node {
    int x, y, deep;
    node(int _x, int _y, int _deep) : x(_x), y(_y), deep(_deep) {}
};

const int kMax = 100 + 10;
const int dx[] = {-1, 1, 0, 0, 0};
const int dy[] = {0, 0, -1, 1, 0};

int n, m, k, d;
bool vis[kMax * 10][kMax][kMax];
queue<node> q;

int get_direction(char ch) {
    if(ch == 'N') return 0;
    if(ch == 'S') return 1;
    if(ch == 'W') return 2;
    return 3;
}

int solve() {
    while(!q.empty()) {
        node t = q.front(); q.pop();
        if(t.deep > d) return -1;//死了
        if(t.x == n && t.y == m) return t.deep;//逃出生天
        for(int i = 0;i < 5;++ i) {//尝试五个搜索出口
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x >= 0 && x <= n && y >= 0 && y <= m &&
              !vis[t.deep + 1][x][y]) {
                q.push({x, y, t.deep + 1});
                vis[t.deep + 1][x][y] = true;
            }
        }
    }
    return -1;
}

int main() {
    char ch;
    int c, t, v, x, y;
    scanf("%d%d%d%d", &n, &m, &k, &d);//n+1行,m+1列,k个士兵,d个单位能量
    getchar();//吃掉回车符
    for(int i = 0;i < k;++ i) {
        scanf("%c%d%d%d%d", &ch, &t, &v, &x, &y);
        getchar();
        c = get_direction(ch);//方向转化
        for(int j = 0;j <= d;++ j) {//该点有士兵
            vis[j][x][y] = true;
        }
        for(int j = 0;j < d;j += t) {//预处理每个周期所打出的子弹的落点
            for(int a = 1;j + a <= d;++ a) {//计算每个子弹随时刻变化所在的地方
                int tx = x + dx[c] * a * v, ty = y + dy[c] * a * v;//计算坐标
                if(tx < 0 || tx > n || ty < 0 || ty > m) break;
                vis[j + a][tx][ty] = true;//记录时间及坐标
            }
        }
    }
    q.push({0, 0, 0});//起点
    vis[0][0][0] = true;
    int res = solve();
    if(res == -1) printf("Bad luck!\n");
    else printf("%d\n", res);
    return 0;
}

上一篇:

下一篇: