Submission #1216246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216246		trimkus	Maze (JOI23_ho_t3)	C++20	0 / 100	2093 ms	1472 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;
	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<int>> dist(r, vector<int>(c, r * c + 1));
	deque<array<int, 6>> dq;
	dq.push_back({sti, stj, -1, -1, r, c});
	dist[sti][stj] = 0;
	vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
	while (dq.size()) {
		int ri = dq.front()[0];
		int rj = dq.front()[1];
		int mxi = dq.front()[2];
		int mxj = dq.front()[3];
		int mni = dq.front()[4];
		int mnj = dq.front()[5];
		dq.pop_front();
		for (int k = 0; k < 4; ++k) {
			int ni = ri + dx[k];
			int nj = rj + dy[k];
			if (ni < 0 || nj < 0 || ni >= r || nj >= c) continue;
			int nmxi = max(mxi, ni);
			int nmni = min(mni, ni);
			int nmxj = max(mxj, nj);
			int nmnj = min(mnj, nj);
			int add = ((nmxi - nmni >= N || nmxj - nmnj >= N) && a[ni][nj] == '#');
			if (a[ni][nj] == '#' && a[ri][rj] == '.') add = 1;
			if (add == 0) {
				if (dist[ni][nj] > dist[ri][rj]) {
					dist[ni][nj] = dist[ri][rj];
					if (a[ni][nj] == '#') dq.push_front({ni, nj, nmxi, nmxj, nmni, nmnj});
					else dq.push_front({ni, nj, -1, -1, r, c});
				}
			} else {
				if (dist[ni][nj] > dist[ri][rj] + add) {
					dist[ni][nj] = dist[ri][rj] + add;
					dq.push_front({ni, nj, ni, nj, ni, nj});
				}
			}
		}
	}
	//~ for (int i = 0; i < r; ++i) {
		//~ for (int j = 0; j < c; ++j) {
			//~ cout << dist[i][j] << " ";
		//~ }
		//~ cout << "\n";
	//~ }
	cout << dist[eni][enj] << "\n";
}

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