RE求助
查看原帖
RE求助
757870
Essenza楼主2024/10/3 15:25
#include<bits/stdc++.h>
using namespace std;

const int N = 5005;

bool vis[N][N];
int n, m;
int sx, sy, ex, ey;
char c[N][N];

int dx[5] = { +0,+0,+1,-1 };
int dy[5] = { +1,-1,+0,+0 };

int cnt_t;
int dis[N][N];

struct node {
	int x, y;
}t[N * N];

queue<node>fdq;

bool check(int x, int y,node now) {
	if (x >= 1 && x <= n && y >= 1 && y <= m && dis[x][y] > dis[now.x][now.y] + 1) return true;
	return false;
}

void find_dist() {
	while (!fdq.empty()) {
		node t = fdq.front();
		fdq.pop();
		for (int i = 0; i < 4; i++) {
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			if (check(nx, ny, t)) {
				dis[nx][ny] = dis[t.x][t.y] + 1;
				fdq.push({ nx, ny });
			}
		}
	}
	return;
}

bool check3(int x, int y,int ch_dis) {
	if (x >= 1 && x <= n && y >= 1 && y <= m && dis[x][y] >= ch_dis && vis[x][y] == false) return true;
	return false;
}

bool check2(int x) {
	queue<node>q;
	memset(vis, false, sizeof(vis));
	q.push({ sx,sy });
	while (!q.empty()) {
		node t = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			if (check3(nx, ny, x)) {
				if (nx == ex && ny == ey)return true;
				q.push({ nx,ny });
				vis[nx][ny] = true;
			}
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dis[i][j] = INT_MAX;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; i <= m; j++) {
			cin >> c[i][j];
			if (c[i][j] == 'V') {
				sx = i, sy = j;
			}
			else if (c[i][j] == 'J') {
				ex = i, ey = j;
			}
			else if (c[i][j] == '+') {
				cnt_t++;
				t[cnt_t].x = i;
				t[cnt_t].y = j;
				dis[i][j] = 0;
				fdq.push({ i,j });
			}
		}
		cout << endl;
	}

	find_dist();

	int l = 0, r = dis[sx][sy], mid;
	while (l < r) {
		mid = (l + r) >> 1;
		if (check2(mid)) l = mid;
		else r = mid - 1;
	}

	cout << r;

	return 0;
}
2024/10/3 15:25
加载中...