Submission #1080546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080546		TAhmed33	Maze (JOI23_ho_t3)	C++98	100 / 100	790 ms	96036 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
const int inf = 1e9;
int n, m, K;
pair <int, int> s, g;
vector <vector <char>> a;
vector <vector <bool>> vis;
vector <vector <int>> dist;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
bool valid (int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < m && !vis[x][y];
}
void solve () {
	cin >> n >> m >> K;
	cin >> s.first >> s.second;
	cin >> g.first >> g.second;
	s.first--; s.second--; g.first--; g.second--;
	a.resize(n, vector <char> (m));
	vis.resize(n, vector <bool> (m, false));
	dist.resize(n, vector <int> (m, inf));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			vis[i][j] = 0;
		}
	}
	vis[s.first][s.second] = 1; 
	dist[s.first][s.second] = 0;
	deque <pair <int, int>> cur;
	cur.push_back(s);
	int rem = n * m - 1;
	int ss = 0;
	while (rem > 0) {
/*		cout << rem << '\n';
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << vis[i][j];
			}
			cout << '\n';
		}
		cout << '\n';*/
		if (cur.empty()) {
			break;
		}
		deque <array <int, 4>> dd;
		while (!cur.empty()) {
			auto k = cur.front();
			cur.pop_front();
			//cout << k.first << " " << k.second << '\n';
			bool flag = 0;
			for (int i = 0; i < 4; i++) {
				int x = k.first + dx[i];
				int y = k.second + dy[i];
				if (!valid(x, y)) {
					continue;
				}
				if (a[x][y] == '.') {
					dist[x][y] = ss;
					vis[x][y] = 1;
					cur.push_back({x, y});
					rem--;
				} else {
					flag = 1;
				}
			}
			if (flag) {
				dd.push_back({k.first, k.second, 0, 0});
			}
		}
		ss++;
		while (!dd.empty()) {
			auto k = dd.front();
			dd.pop_front();
			bool flag = 0;
			for (int i = 0; i < 4; i++) {
				array <int, 4> g = {k[0] + dx[i], k[1] + dy[i], k[2] + abs(dx[i]), k[3] + abs(dy[i])};
/*				for (auto j : k) cout << j << " ";
				cout << '\n';
				cout << ": \n";
				for (auto k : g) {
					cout << k << " ";
				}
				cout << '\n' << '\n';*/
				if (valid(g[0], g[1]) && g[2] <= K && g[3] <= K && g[2] + g[3] < 2 * K) {
					vis[g[0]][g[1]] = 1;
					dist[g[0]][g[1]] = ss;
					dd.push_back(g);
					rem--;
				}
			}
			if (!flag) {
				cur.push_back({k[0], k[1]});
			}
		}
	}	
	cout << dist[g.first][g.second] << '\n';
}				
signed main () {
	 #ifndef ONLINE_JUDGE 
		//freopen("input_file", "r", stdin);
		//freopen("output_file", "w", stdout);
	#endif
	//ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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