A* 90分 (#8 WA) 求调
查看原帖
A* 90分 (#8 WA) 求调
601527
zhuzl009楼主2024/8/27 00:01
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

const int N = 1e3 + 5;

string a[N];
int mhd[N][N], dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int stx, sty, edx, edy;
int n, ans = 1e9 + 5;
bool vis[N][N];

struct node {
	int x, y, step;
	friend bool operator > (const node nd1, const node nd2) {
		return nd1.step + mhd[nd1.x][nd1.y] > nd2.step + mhd[nd2.x][nd2.y];
	}
} chos[5];

priority_queue<node, vector<node>, greater<node>> q;

int Astar() {
	q.push({stx, sty, 0}), vis[stx][sty] = true;
	while (!q.empty()) {
		node t = q.top();
		q.pop();

		if (t.x == edx && t.y == edy)
			return t.step;

		for (int i = 0; i < 4; i ++) {
			int dx = t.x + dir[i][0], dy = t.y + dir[i][1];
			if (dx > 0 && dx <= n && dy > 0 && dy <= n && !vis[dx][dy] && a[dx][dy] == '0')
				vis[dx][dy] = true, q.push({dx, dy, t.step + 1});
		}
	}
	return -1;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], a[i] = ' ' + a[i];

	cin >> stx >> sty >> edx >> edy;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)
			mhd[i][j] = abs(edx - i) + abs(edy - j);

	cout << Astar();
}
2024/8/27 00:01
加载中...