A*搜索
代码演示
#include <iostream>
#include <queue>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct Node {
int x, y, step;
double dis;
bool operator< (const Node &a) const {
return this->step + this->dis > a.step + a.dis;
}
};
int n, m, sx, sy, tx, ty, cnt;
int dis[8][2] = {1, 1, 1, -1, 1, 0, -1, -1, -1, 1, -1, 0, 0, 1, 0, -1};
char mmap[102][102];
int ans[102][102][2];
double func(int x, int y) {
int t1 = x - tx;
int t2 = y - ty;
return sqrt(t1 * t1 + t2 * t2);
}
void func2(int x, int y) {
if (mmap[x][y] == 'S') {
return ;
}
mmap[x][y] = 'o';
func2(ans[x][y][0], ans[x][y][1]);
return ;
}
void p_out() {
printf("............................cnt = %d ............................\n", cnt);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << mmap[i][j];
if (mmap[i][j] == 'x') mmap[i][j] = 'X';
}
cout << endl;
}
printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");
return ;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mmap[i][j];
if (mmap[i][j] == 'S') sx = i, sy = j;
if (mmap[i][j] == 'T') tx = i, ty = j;
}
}
priority_queue <Node> q;
q.push((Node){sx, sy, 0, func(sx, sy)});
while (!q.empty()) {
Node tp = q.top();
q.pop();
for (int i = 0; i < 8; i++) {
int dx = tp.x + dis[i][0];
int dy = tp.y + dis[i][1];
if (mmap[dx][dy] == 'T') {
func2(tp.x, tp.y);
p_out();
cout << tp.step + 1 << endl;
return 0;
}
if (mmap[dx][dy] == '.') {
mmap[dx][dy] = 'x';
cnt++;
if (cnt % 10 == 0) {
p_out();
}
ans[dx][dy][0] = tp.x;
ans[dx][dy][1] = tp.y;
q.push((Node){dx, dy, tp.step + 1, func(dx, dy)});
}
}
}
return 0;
}