60pts MLE求条
查看原帖
60pts MLE求条
1137373
zhangzirui66楼主2024/10/3 11:25
#include<bits/stdc++.h>
using namespace std;
int n, m, stx, sty, edx, edy;
char c[505][505];
struct node{
	int x, y, j;
	bool operator < (const node &tmp) const{
		return j < tmp.j;
	} 
};
struct node2{
	int x, y;
};
int head, tail = -1;
int dis[505][505];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
bool vis[505][505];
queue<node2> q;
void bfs(){
	while(q.size()){
		node2 t = q.front(); q.pop();
		for(int i = 0; i < 4; i ++){
			int tx = t.x + dx[i], ty = t.y + dy[i];
			if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && c[tx][ty] != 'H' && dis[tx][ty] == 2e9){
				dis[tx][ty] = dis[t.x][t.y] + 1;
				q.push({tx, ty});
			}
		}
	}
}
int bfs2(){
	priority_queue<node> q;
	int ans = 2e9;
	q.push({stx, sty, dis[stx][sty]}); vis[stx][sty] = 1;
	while(q.size()){
		node now = q.top(); q.pop();
		vis[now.x][now.y] = 1;
		if(now.x == edx && now.y == edy) ans = min(ans, now.j);
		for(int i = 0; i < 4; i ++){
			int tx = now.x + dx[i], ty = now.y + dy[i];
			if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && !vis[tx][ty]){
				q.push({tx, ty, min(dis[tx][ty], now.j)});
			}
		}
	}
	return ans;
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++){
			cin >> c[i][j], dis[i][j] = 2e9;
			if(c[i][j] == '+') dis[i][j] = 0, q.push({i, j});
			if(c[i][j] == 'V') stx = i, sty = j;
			if(c[i][j] == 'J') edx = i, edy = j;
		}
	bfs();
	cout << bfs2();
	return 0;
}

32MB空间太少了吧。

2024/10/3 11:25
加载中...