Submission #64540865


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1087;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
char g[N][N];
int n, m;
vector<pair<int,int>> h[N*N];
const int inf = N * N;
int dist[N * N];
int id(int x, int y) {
	return x * m + y;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> g[i];
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; ++j) {
			int u = id(i, j);
			if (g[i][j] == '.') {
				for (int k = 0; k < 4; ++k) {
					int x = i + dx[k];
					int y = j + dy[k];
					int v = id(x, y);
					if (min(x, y) < 0 || x >= n || y >= m)
						continue;
					if (g[x][y] == '.') {
						h[u].emplace_back(0, v);
					} 
				}
			} else {
				for (int k = 0; k < 4; ++k) {
					for (int s = 1; s <= 2; ++s) {
						int x = i + dx[k] * s;
						int y = j + dy[k] * s;
						int v = id(x, y);
						if (min(x, y) < 0 || x >= n || y >= m)
							continue;
						if (g[x][y] == '.') {
							h[v].emplace_back(1, u);
							h[u].emplace_back(s - 1, v);
						} else {
							h[u].emplace_back(1, v);
						}
					}
				}
			}
		}
	}
	--a, --b, --c, --d;
	int s = id(a, b);
	int t = id(c, d);
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	fill_n(dist, n * m, inf);
	dist[s] = 0;
	pq.emplace(0, s);
	while (pq.size()) {
		int w, u;
		tie(w, u) = pq.top();
		pq.pop();
		if (w != dist[u])
			continue;
		for (auto [x, v] : h[u]) {
			int nw = w + x;
			if (nw < dist[v]) {
				dist[v] = nw;
				pq.emplace(nw, v);
			}
		}
	}
	cout << dist[t] << '\n';
}

Submission Info

Submission Time
Task D - Takahashi the Wall Breaker
User pr3pony
Language C++ 17 (gcc 12.2)
Score 400
Code Size 1702 Byte
Status AC
Exec Time 352 ms
Memory 114316 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 34
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt, example_03.txt
All example_00.txt, example_01.txt, example_02.txt, example_03.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt
Case Name Status Exec Time Memory
example_00.txt AC 15 ms 31240 KiB
example_01.txt AC 15 ms 31216 KiB
example_02.txt AC 15 ms 31076 KiB
example_03.txt AC 16 ms 31220 KiB
hand_00.txt AC 241 ms 114296 KiB
hand_01.txt AC 261 ms 114304 KiB
hand_02.txt AC 257 ms 114252 KiB
hand_03.txt AC 242 ms 114244 KiB
hand_04.txt AC 252 ms 114316 KiB
hand_05.txt AC 192 ms 98796 KiB
hand_06.txt AC 190 ms 98788 KiB
hand_07.txt AC 222 ms 102476 KiB
hand_08.txt AC 153 ms 83012 KiB
hand_09.txt AC 15 ms 31164 KiB
random_00.txt AC 253 ms 109584 KiB
random_01.txt AC 297 ms 108044 KiB
random_02.txt AC 297 ms 111320 KiB
random_03.txt AC 274 ms 110960 KiB
random_04.txt AC 277 ms 106344 KiB
random_05.txt AC 271 ms 106820 KiB
random_06.txt AC 307 ms 109728 KiB
random_07.txt AC 304 ms 109244 KiB
random_08.txt AC 268 ms 100744 KiB
random_09.txt AC 306 ms 107892 KiB
random_10.txt AC 282 ms 102784 KiB
random_11.txt AC 335 ms 109820 KiB
random_12.txt AC 342 ms 111088 KiB
random_13.txt AC 352 ms 110240 KiB
random_14.txt AC 283 ms 108712 KiB
random_15.txt AC 318 ms 112684 KiB
random_16.txt AC 318 ms 110532 KiB
random_17.txt AC 256 ms 109388 KiB
random_18.txt AC 309 ms 110064 KiB
random_19.txt AC 292 ms 111300 KiB