深入虎穴pta算法分析
时间: 2023-07-19 13:23:03 浏览: 115
深入虎穴是一道经典的算法题,需要使用图论相关知识进行解答。
题目描述:
有一只老虎,它在一个 $N \times M$ 的网格状森林中漫步,每个格子可能是草地、灌木丛或者陷阱。老虎只能在草地和灌木丛上行走,陷阱则不能进入。老虎每一步可以向上、下、左、右四个方向行走,每一步的代价为 $1$。若老虎走到了一个灌木丛,它会感到非常愉悦,代价为 $0$;若老虎走到了一个草地,它则会感到一般般,代价为 $1$。老虎的目的是从森林的左上角走到右下角,求老虎走到终点的最小代价。
算法分析:
这是一道典型的最短路径问题,可以使用图论中的 Dijkstra 算法或者 A* 算法进行解答。我们可以将森林看做一个带权无向图,其中草地和灌木丛之间连有权值为 $1$ 的边,陷阱不连边。然后以左上角为起点,右下角为终点,使用 Dijkstra 算法或者 A* 算法求解最短路径即可。
代码实现:
这里给出 Dijkstra 算法的代码实现,时间复杂度为 $O(NM \log NM)$。
```cpp
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int N, M;
int maze[MAXN][MAXN];
int dis[MAXN * MAXN];
bool vis[MAXN * MAXN];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
struct Node {
int x, y, d;
bool operator < (const Node &rhs) const {
return d > rhs.d;
}
};
int dijkstra() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
priority_queue<Node> pq;
dis[0] = 0;
pq.push({0, 0, 0});
while (!pq.empty()) {
Node u = pq.top(); pq.pop();
if (vis[u.x * M + u.y]) continue;
vis[u.x * M + u.y] = true;
for (int i = 0; i < 4; i++) {
int nx = u.x + dx[i];
int ny = u.y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (maze[nx][ny] == 2) continue;
int nd = u.d + maze[nx][ny];
if (dis[nx * M + ny] > nd) {
dis[nx * M + ny] = nd;
pq.push({nx, ny, nd});
}
}
}
return dis[(N - 1) * M + M - 1];
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> maze[i][j];
}
}
int ans = dijkstra();
cout << ans << endl;
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)