A*寻路算法
#include<bits/stdc++.h>
using namespace std;
class node {
public:
int row;
int col;
int step;
// 启发函数 -> 估计代价
int h;
// 耗散函数 -> 实际代价
int g;
int val;
node(){}
node(int row, int col, int val) {
this->row = row;
this->col = col;
this->val = val;
this->step = val == 1 ? -1 : INT_MAX;
this->h = -1;
this->g = val == 1 ? -1 : INT_MAX;
}
bool operator>(const node& other) const {
return h + g > other.h + other.g;
}
int getF(){
return h + g;
}
void updateStep(node point) {
step = point.step + 1;
}
void setH(node point) {
h = abs(row - point.row) + abs(col - point.col);
}
void setG(node point) {
g = point.g + 1;
}
};
struct mv {
int dx;
int dy;
};
int main () {
vector<mv> d = {{1, 0},{-1, 0},{0, 1},{0, -1}};
// 读取数据
int n, m;
cin >> n >> m;
vector<vector<node>> matfix(n,vector<node>(m));
for(int i = 0;i < n; i++) {
for(int j = 0;j < m; j++) {
int val; cin >> val;
matfix[i][j] = node(i,j,val);
}
}
// 初始化
int min_steps = -1;
int sx, sy;
int ex, ey;
cin >> sx >> sy >> ex >> ey;
node& start = matfix[sx][sy];
node& end = matfix[ex][ey];
start.setH(end);
start.g = 0;
start.step = 0;
priority_queue<node,vector<node>,greater<node>> pq;
pq.push(start);
// Astar
while(pq.size() > 0) {
node now = pq.top();
pq.pop();
if (now.g > matfix[now.row][now.col].g) continue;
matfix[now.row][now.col] = now;
if(now.row == ex && now.col == ey) {
min_steps = now.step;
break;
}
for(auto &[dx,dy]: d) {
int x = now.row + dx;
int y = now.col + dy;
if(x >= 0 && x < n && y >= 0 && y < m) {
node& run = matfix[x][y];
if ((run.g == INT_MAX || run.g > now.g + 1) && run.val != 1) {
run.setH(end);
run.setG(now);
run.updateStep(now);
pq.push(run);
}
}
}
}
// 输出 N W
for(int i = 0;i < n; i++) {
for(int j = 0;j < m; j++) {
int v = matfix[i][j].step;
if(v == INT_MAX) {
cout << "N";
}else if(v == -1) {
cout << "W";
}else {
cout << v;
}
cout << "\t";
}
cout << endl;
}
if(min_steps != -1) {
cout << "最少" << min_steps << "步走过迷宫";
}else {
cout << "找不到目标";
}
}
- 感谢你赐予我前进的力量
赞赏者名单
因为你们的支持让我意识到写文章的价值🙏
本文是原创文章,采用 CC BY-NC-ND 4.0 协议,完整转载请注明来自 葡萄w
评论
匿名评论
隐私政策
你无需删除空行,直接评论以获取最佳展示效果