Submission #1216303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216303		trimkus	Maze (JOI23_ho_t3)	C++20	100 / 100	457 ms	147072 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;




int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int r, c, N;
	cin >> r >> c >> N;
	int sti, stj, eni, enj;
	cin >> sti >> stj >> eni >> enj;
	sti -= 1;
	stj -= 1;
	eni -= 1;
	enj -= 1;
	N -= 1;
	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<array<int, 3>>> dist(r, vector<array<int, 3>>(c, {r * c + 1, -1, -1}));
	vector<array<int, 2>> q1, q2;
	auto push = [&](vector<array<int, 2>>& q, int i, int j, int x, int y, int z) -> void {
		if (i < 0 || j < 0 || i >= r || j >= c) return;
		if (dist[i][j][0] <= x) return;
		dist[i][j] = {x, y, z};
		q.push_back({i, j});
	};
	auto push2 = [&](int i, int j, int x) -> void {
		if (i < 0 || j < 0 || i >= r || j >= c) return;
		if (a[i][j] == '#') push(q2, i, j, x + 1, N, N);
		else push(q1, i, j, x, 0, 0);
	};
	push(q1, sti, stj, 0, 0, 0);
	while (q1.size()) {
		for (int it = 0; it < (int)q1.size(); ++it) {
			auto [i, j] = q1[it];
			auto [x, y, z] = dist[i][j];
			if (y > 0) {
				push(q1, i - 1, j, x, y - 1, z);
				push(q1, i + 1, j, x, y - 1, z); 
			}
			if (z > 0) {
				push(q1, i, j - 1, x, y, z - 1);
				push(q1, i, j + 1, x, y, z - 1);
			}
		}
		for (int it = 0; it < (int)q1.size(); ++it) {
			auto [i, j] = q1[it];
			auto [x, y, z] = dist[i][j];
			
		}
		for (int it = 0; it < (int)q1.size(); ++it) {
			auto [i, j] = q1[it];
			//~ cout << i << " " << j << "\n";
			auto [x, y, z] = dist[i][j];
			push2(i - 1, j, x);
			push2(i + 1, j, x);
			push2(i, j - 1, x);
			push2(i, j + 1, x);
		}
		swap(q1, q2);
		q2.clear();
	}
	cout << dist[eni][enj][0] << "\n";
	
}

• 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