제출 #1263554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263554		kustov_vadim_533	Maze (JOI23_ho_t3)	C++20	100 / 100	812 ms	102876 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

template<typename T>
ostream& operator<<(ostream& out, const vector<T> &a){
	for  (auto& x : a){
		out << x << ' ';
	}
	out << '\n';
	return out;
}

template<typename T>
istream& operator>>(istream& in, vector<T> &a){
	for (size_t i = 0; i < a.size(); ++i){
		in >> a[i];
	}
	return in;
}

mt19937 gen;

int di[4] = {0, 0, -1, 1};
int dj[4] = {-1, 1, 0, 0};

int r, c;
vector<vector<bool>> us;
vector<vector<int>> ni, nj;

int get_ni(int i, int j){
	if (i >= r || !us[i][j]) return i;
	ni[i][j] = get_ni(ni[i][j], j);
	return ni[i][j];
};

int get_nj(int i, int j){
	if (j >= c || !us[i][j]) return j;
	nj[i][j] = get_nj(i, nj[i][j]);
	return nj[i][j];
};

inline void solve() {
	int n;
	cin >> r >> c >> n;
	
	int sr, sc, gr, gc;
	cin >> sr >> sc >> gr >> gc;

	--sr, --sc, --gr, --gc;

	vector<vector<char>> a(r, vector<char>(c));

	for (int i = 0; i < r; ++i){
		for (int j = 0; j < c; ++j){
			cin >> a[i][j];
		}
	}

	us.assign(r, vector<bool>(c, false));

	ni.assign(r, vector<int>(c));
	nj.assign(r, vector<int>(c));

	for (int i = 0; i < r; ++i){
		for (int j = 0; j < c; ++j){
			ni[i][j] = i + 1;
			nj[i][j] = j + 1;
		}
	}

	queue<pair<int, int>> q1, q2;

	us[sr][sc] = true;
	q1.push({sr, sc});

	int ans = 0;
	while (true){
		while (!q1.empty()){
			pair<int, int> v = q1.front();
			q2.push(v);
			q1.pop();

			for (int w = 0; w < 4; ++w){
				int ui = v.first + di[w];
				int uj = v.second + dj[w];

				if (ui < 0 || ui >= r || uj < 0 || uj >= c || a[ui][uj] == '#' || us[ui][uj]) continue;

				us[ui][uj] = true;

				q1.push({ui, uj});
			}
		}

		if (us[gr][gc]){
			cout << ans << '\n';
			break;
		}

		++ans;

		while (!q2.empty()){
			pair<int, int> v = q2.front();
			q2.pop();

			if (abs(v.first - gr) <= n && abs(v.second - gc) <= n && abs(v.first - gr) + abs(v.second - gc) <= 2 * n - 1){
				us[gr][gc] = true;
			}

			int il = max(v.first - n, 0);
			int ir = min(v.first + n, r - 1);

			int jl = max(v.second - n, 0);
			int jr = min(v.second + n, c - 1);

			int i, j;

			i = il, j = jl;
			for (i = get_ni(i, j); i <= ir; i = get_ni(i, j)){
				if (abs(i - v.first) + abs(j - v.second) >= 2 * n) {
					++i;
					continue;
				}
				us[i][j] = true;
				q1.push({i, j});
			}
			i = il, j = jr;
			for (i = get_ni(i, j); i <= ir; i = get_ni(i, j)){
				if (abs(i - v.first) + abs(j - v.second) >= 2 * n) {
					++i;
					continue;
				}
				us[i][j] = true;
				q1.push({i, j});
			}
			i = il, j = jl;
			for (j = get_nj(i, j); j <= jr; j = get_nj(i, j)){
				if (abs(i - v.first) + abs(j - v.second) >= 2 * n) {
					++j;
					continue;
				}
				us[i][j] = true;
				q1.push({i, j});
			}
			i = ir, j = jl;
			for (j = get_nj(i, j); j <= jr; j = get_nj(i, j)){
				if (abs(i - v.first) + abs(j - v.second) >= 2 * n) {
					++j;
					continue;
				}
				us[i][j] = true;
				q1.push({i, j});
			}
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6