Submission #1263549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263549		kustov_vadim_533	Maze (JOI23_ho_t3)	C++20	67 / 100	2095 ms	14292 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};

inline void solve() {
	int r, c, 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];
		}
	}

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

	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);

			for (int i = il; i <= ir; ++i){
				bool fl = (i == il || i == ir);
				for (int j = jl; j <= jr;){
					if (!us[i][j] && abs(i - v.first) + abs(j - v.second) < 2 * n){
						q1.push({i, j});
						us[i][j] = true;
					}
					if (fl){
						++j;
					}
					else{
						j += jr - jl;
					}
				}
			}
		}
	}
}

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: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6