#7#9怎么改都tle了,求救
查看原帖
#7#9怎么改都tle了,求救
697282
bbqq楼主2023/3/30 14:15
#include <iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n, m;
int map[550][550];//0是墙,1是空地,2是树
int dis[550][550];//表示与树的曼哈顿距离,0表示未知,-1表示就是树
int vis[550][550];//0未访问
int a, b;//狼的坐标
int x, y;//窝的坐标
typedef pair<int, int> P;
vector<P> tree;//所有树的坐标

int getdis(int i, int j) {
	if (dis[i][j] != 0)
		return dis[i][j];
	int mind = 99999999;
	for (auto t : tree) {
		mind = min(mind, abs(t.first - i) + abs(t.second - j));
	}
	dis[i][j] = mind;
	return mind;
}
bool check(int d) {
	queue<P> st;
	memset(vis, 0, sizeof(vis));
	st.emplace(a, b);
	int i, j;
	while (!st.empty()) {
		i = st.front().first, j = st.front().second;
		st.pop();
		if (getdis(i, j) < d)
			continue;
		if (i == x && j == y) {
			return 1;
		}
		if (map[i + 1][j] > 0 && vis[i + 1][j] == 0) {
			st.emplace(i + 1, j);
			vis[i + 1][j] = 1;
		}
		if (map[i][j + 1] > 0 && vis[i][j + 1] == 0) {
			st.emplace(i, j + 1);
			vis[i][j + 1] = 1;
		}
		if (map[i - 1][j] > 0 && vis[i - 1][j] == 0) {
			st.emplace(i - 1, j);
			vis[i - 1][j] = 1;
		}
		if (map[i][j - 1] > 0 && vis[i][j - 1] == 0) {
			st.emplace(i, j - 1);
			vis[i][j - 1] = 1;
		}
	}
	return 0;
}
int main()
{
	cin >> n >> m;
	char t;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> t;
			map[i][j] = 1;
			if (t == 'V')
				a = i, b = j;
			else if (t == 'J')
				x = i, y = j;
			else if (t == '+') {//树
				map[i][j] = 2;
				dis[i][j] = -1;
				tree.emplace_back(i, j);
			}
		}
	}
	int l = 0, r = min(getdis(a, b), getdis(x, y)), mid;
	while (l < r) {
		mid = (l + r + 1) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid - 1;
	}
	cout << l;
	return 0;
}
2023/3/30 14:15
加载中...