题目

{% fold 点击显/隐题目 %}

在一片广阔的土地上，有一个鸟人，他需要从这里穿过原野，回到基地。这片原野上，有平地(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
{% endfold %}

题解

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

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

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

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

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

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

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

两种移动方式要分开写，步行就是通常bfs的那种拓展节点的方式，飞行需要在那个基础上加上一个循环变量 k (飞行距离)。k要满足 k<d ，同时当发现已经飞到地图外时就可以直接break了。

整体而看，只是一个 vis 变量多了一维的普通 bfs ，不要想复杂了

代码

{% fold 点击显/隐代码 %}```cpp 飞跃原野 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
#include
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 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;
}

{% endfold %}