제출 #1121714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121714		stefanneagu	Maze (JOI23_ho_t3)	C++17	8 / 100	693 ms	198788 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
int dx[] = {1, -1, 0,  0};
int dy[] = {0, 0,  -1, 1};
 
vector<vector<char>> v;
vector<vector<int>> dp;
vector<set<int>> s;
queue<pair<int, int>> q;
 
int f[101][101];
 
void flood_fill(int i, int j, int val) {
	for(int d = 0; d < 4; d++) {
		int a = i + dx[d];
		int b = j + dy[d];
		if(v[a][b] == '.' && s[a].find(b) != s[a].end()) {
			q.push({a, b});
			s[a].erase(b);
			dp[a][b] = val;
			flood_fill(a, b, val);
		}
	}
}
 
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int n, m, d;
	cin >> n >> m >> d;
	v.resize(n + 2, vector<char>(m + 2));
	dp.resize(n + 2, vector<int>(m + 2));
	s.resize(n + 2);
	int si, sj, ei, ej;
	cin >> si >> sj >> ei >> ej;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> v[i][j];
			s[i].insert(j);
			dp[i][j] = 1e9;
		}
	}
	dp[si][sj] = 0;
	s[si].erase(sj);
	q.push({si, sj});
	flood_fill(si, sj, 0);
	while(!q.empty()) {
		auto [a, b] = q.front();
		q.pop();
		if(a == ei && b == ej) {
			cout << dp[a][b];
			return 0;
		}
		// deci mergem (a - d, b - d) -> (a + d, b + d) 
		// fara colturi
		int p1 = b - d, p2 = b + d, aux;
		for(int i = max(1, a - d); i <= min(n, a + d); i++) {
			if(i == a - d || i == a + d) {
				p1++, p2--;
			}
			auto it = s[i].lower_bound(p1);
			vector<int> de;
			while(it != s[i].end() && *it <= p2) {
				aux = *it;
				it++;
				s[i].erase(aux);
				dp[i][aux] = dp[a][b] + 1;
				q.push({i, aux});
				for(int dir = 0; dir < 4; dir++) {
					int ii = i + dx[dir];
					int jj = aux + dy[dir];
					if(v[ii][jj] == '.' && s[ii].find(jj) != s[ii].end()) {
						// continue;
						s[ii].erase(jj);
						dp[ii][jj] = dp[i][aux];
						q.push({ii, jj});
						flood_fill(ii, jj, dp[ii][jj]);
					}
				}
				if(v[i][aux] == '.') {
					flood_fill(i, aux, dp[i][aux]);
				}
			}
			if(i == a - d || i == a + d) {
				p1--, p2++;
			}
		}
	}
	assert(0);
	return 0;
}

• 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