Submission #1216262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216262		trimkus	Maze (JOI23_ho_t3)	C++20	8 / 100	60 ms	13484 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));
	dist[sti][stj] = 0;
	deque<array<int, 2>> dq;
	dq.push_front({sti, stj});
	vector<int> dx = {0, 1, -1, 0}, dy = {1, 0, 0, -1};
	while (dq.size()) {
		int i = dq.front()[0];
		int j = dq.front()[1];
		dq.pop_front();
		for (int k = 0; k < 4; ++k) {
			int ni = i + dx[k];
			int nj = j + dy[k];
			if (ni < 0 || nj < 0 || ni >= r || nj >= c) continue;
			int add = (a[ni][nj] == '#');
			if (dist[ni][nj] > dist[i][j] + add) {
				dist[ni][nj] = dist[i][j] + add;
				if (add) dq.push_back({ni, nj});
				else dq.push_front({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: 8 / 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