Submission #1121390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121390		stefanneagu	Maze (JOI23_ho_t3)	C++17	51 / 100	2054 ms	200688 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;
				dp[i][aux] = dp[a][b] + 1;
				q.push({i, aux});
				if(v[i][aux] == '.' || v[i][aux - 1] == '.' || v[i - 1][aux] == '.'|| v[i][aux + 1] == '.' || v[i + 1][aux] == '.') {
					de.push_back(aux);
				}
				it++;
				s[i].erase(aux);
			}
			for(auto ip : de) {
				for(int dir = 0; dir < 4; dir++) {
					int ii = i + dx[dir];
					int jj = ip + dy[dir];
					if(v[ii][jj] == '.' && s[ii].find(jj) != s[ii].end()) {
						// continue;
						s[ii].erase(jj);
						dp[ii][jj] = dp[i][ip];
						q.push({ii, jj});
						flood_fill(ii, jj, dp[ii][jj]);
					}
				}
				if(v[i][ip] == '.' && s[i].find(ip) != s[i].end()) {
					s[i].erase(ip);
					flood_fill(i, ip, dp[i][ip]);
				}
			}
			if(i == a - d || i == a + d) {
				p1--, p2++;
			}
		}
	}
	assert(0);
  return 0;
}

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