AOJ 866.飞跃原野

135


题目



点击显/隐题目

在一片广阔的土地上,有一个鸟人,他需要从这里穿过原野,回到基地。这片原野上,有平地(P)、有湖泊(L),因为鸟人可以飞,所以呢,有的时候,他可以飞越湖泊。现在,鸟人需要用最快的时间,回到基地。
假设原野是一个m*n的矩阵,有两种地形,用P和L表示。鸟人只能停留在平地上。他目前处在(1,1)这个位置,而目的地是(m,n)。他可以向上下左右四个方向移动,或者飞行。每移动一格需要1个单位时间。而飞行无论飞多远,都只需要1个单位时间。飞行的途中不可以变方向,也就是说飞行也只能是上下左右四个方向。并且一次飞行最终必须降落在平地上。当然,受到能量的限制,鸟人不能无限制的飞行,他总共最多可以飞行的距离为D。


第一行是三个整数,m,n,D,三个数都不超过100,下面是一个m*n的矩阵,表示原野


一个整数,为最短时间,如果无法到达,则输出“impossible”


Original Transformed
4 4 2
PLLP
PPLP
PPPP
PLLP


Original Transformed
5




题解


有两种移动方式的最短路问题

  • 步行:上下左右移动一格,只能通过平原。时间-1s
  • 飞行:上下左右移动任意格,可以穿越湖泊和平原,但是起点和终点必须是平原。能量减少移动的格数,时间-1s
  • 显然如果有足够的能量的情况下,应该尽可能多的采用飞行的方式(比较快,而且无视地形)

有一种情况需要考虑,如果终点被湖泊包围,而且能量不是那么充足的情况,需要前期尽可能步行,最后才飞行

由于是最短路问题,尝试用BFS(及其变形)解答

由于是不存在权值的最短路,因此不需要使用priority_queue,直接普通的先进先出即可

数组需要对x,y,d同时进行判重,也即 bool vis[101][101][101];

判断是否访问过要在插入队列前,否则会导致 queue 过大

两种移动方式要分开写,步行就是通常bfs的那种拓展节点的方式,飞行需要在那个基础上加上一个循环变量 k (飞行距离)。k要满足 k
整体而看,只是一个 vis 变量多了一维的普通 bfs ,不要想复杂了



代码


点击显/隐代码
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int delta[] = {1, -1, 0, 0};
const int maxn = 105;
char Map[maxn][maxn];
bool vis[maxn][maxn][maxn];
int m, n, D;
struct Point {
    int x, y, d, t;
    Point(int _x = 0, int _y = 0, int _d = 0, int _t = 0)
        : x(_x), y(_y), d(_d), t(_t) {}
    bool operator<(const Point &rhs) const {
        if (t == rhs.t)
            return d > rhs.d;
        return t > rhs.t;
    }
};
//判断位置合法性
bool judge(int x, int y) { return (x >= 1 && x <= m && y >= 1 && y <= n); }
queue<Point> Q;
int bfs() {
    while (!Q.empty())
        Q.pop();
    int ans = -1;
    memset(vis, false, sizeof(vis));
    Q.push(Point(1, 1, D, 0));
    vis[1][1][D] = true;
    while (!Q.empty()) {
        int x = Q.front().x;
        int y = Q.front().y;
        int d = Q.front().d;
        int t = Q.front().t;
        Q.pop();
        //printf("x=%d y=%d d=%d t=%d \n", x, y, d, t);
        if (x == m && y == n) {
            ans = t;
            break;
        }
        //步行移动
        for (int i = 0; i < 4; i++) {
            int xx = x + delta[i];
            int yy = y + delta[3 - i];
            if (!judge(xx, yy))
                continue;
            if (Map[xx][yy] != 'P')
                continue;
            if (vis[xx][yy][d])
                continue;
            vis[xx][yy][d] = true;
            Q.push(Point(xx, yy, d, t + 1));
        }
        //飞行移动
        for (int i = 0; i < 4; i++) {
            for (int k = 1; k <= d; k++) {
                int xx = x + delta[i] * k;
                int yy = y + delta[3 - i] * k;
                if (!judge(xx, yy))
                    break;
                if (Map[xx][yy] != 'P')
                    continue;
                if (vis[xx][yy][d - k])
                    continue;
                vis[xx][yy][d - k] = true;
                Q.push(Point(xx, yy, d - k, t + 1));
            }
        }
    }
    return ans;
}
int main() {
#ifdef debug
    freopen("in.txt", "r", stdin);
    int START = clock();
#endif
    cin.tie(0);
    cin.sync_with_stdio(false);
    scanf("%d%d%d", &m, &n, &D);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("\n%c", &Map[i][j]);
            // printf("%c", Map[i][j]);
        }
        // printf("\n");
    }
    int ans = bfs();
    if (ans == -1)
        printf("impossible\n");
    else
        printf("%d\n", ans);
#ifdef debug
    printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论