Submission #1122089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122089		stefanneagu	Maze (JOI23_ho_t3)	C++17	8 / 100	414 ms	25240 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
struct state {
	int a, b, si, sj, ji, jj;
};
 
int dx[] = {1, -1, 0,  0};
int dy[] = {0, 0,  -1, 1};
 
vector<vector<bool>> v, f;
vector<vector<int>> dp; 
 
bool in(int a, int b, int x, int y, int i, int j) {
	if(v[i][j] == 1) {
		return 1;
	}
	if(a <= i && i <= x && b <= j && j <= y) {
		return 1;
	}
	return 0;
}
 
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<bool>(m + 2));
	f.resize(n + 2, vector<bool>(m + 2));
	dp.resize(n + 2, vector<int>(m + 2));
	int s1, s2, e1, e2;
	cin >> s1 >> s2 >> e1 >> e2;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			char ch;
			cin >> ch;
			if(ch == '.') {
				ch = 1;
			} else {
				ch = 0;
			}
			v[i][j] = ch;
			dp[i][j] = 1e9;
		}
	}
	dp[s1][s2] = 0;
	deque<state> dq;
	dq.push_front({s1, s2, -1, -1, -1, -1});
	int val = 0, i, j;
	while(!dq.empty()) {
		auto [a, b, si, sj, ji, jj] = dq.front();
		// cout << a << " " << b << ": " << dp[a][b] << '\n';
		dq.pop_front();
		for(int dd = 0; dd < 4; dd++) {
			i = a + dx[dd];
			j = b + dy[dd];
			if(min(i, j) < 1 || i > n || j > m) {
				continue;
			}
			val = 1 - in(si, sj, ji, jj, i, j);
			if(dp[a][b] + val < dp[i][j]) {
				if(!val) {
					dp[i][j] = dp[a][b];
					dq.push_front({i, j, si, sj, ji, jj});
				} else {
					dp[i][j] = dp[a][b] + 1;
					dq.push_back({i, j, a - d + 1, b - d, a, b - 1});
					dq.push_back({i, j, a, b - d, a + d - 1, b - 1});
					dq.push_back({i, j, a - 1, b - d + 1, a - d, b});
					dq.push_back({i, j, a - 1, b, a - d, b + d - 1});
					dq.push_back({i, j, a, b + 1, a - d + 1, b - d});
					dq.push_back({i, j, a - d + 1, b + 1, a, b + d});
					dq.push_back({i, j, a - d, b, a - 1, b + d - 1});
					dq.push_back({i, j, a - d, b - d + 1, a - 1, b});
				}
			}
		}
	}
	cout << dp[e1][e2];
	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