Submission #1296644

#TimeUsernameProblemLanguageResultExecution timeMemory
1296644kaiboyMaze (JOI23_ho_t3)C++20
8 / 100
252 ms57968 KiB
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int     N = 6000000;
const int ddi[] = { -1, 0, 1, 0 };
const int ddj[] = { 0, 1, 0, -1 };

char tt[N + 1], aa[N + 1];
int dd[N * 5], qu[N * 6], head, cnt;
int n, m, k;

int encode(int i, int j, int z) {
	return (i * m + j) * 5 + z;
}

void upd(int i, int j, int z, int d, int w) {
	int ijz = encode(i, j, z);
	if (dd[ijz] <= (d += w))
		return;
	dd[ijz] = d;
	if (!w)
		qu[--head] = ijz, cnt++;
	else
		qu[head + cnt++] = ijz;
}

void updsq(int il, int ir, int jl, int jr, int d) {
	if (ir < 0 || n <= il || jr < 0 || m <= jl)
		return;
	il = max(il, 0);
	ir = min(ir, n - 1);
	jl = max(jl, 0);
	jr = min(jr, m - 1);
	if ((il + k - 1) / k * k <= ir && (jl + k - 1) / k * k <= jr)
		upd(il, jl, 1, d, 1);
	if ((il + k - 1) / k * k <= ir && jr / k * k >= jl)
		upd(il, jr, 2, d, 1);
	if (ir / k * k >= il && (jl + k - 1) / k * k <= jr)
		upd(ir, jl, 3, d, 1);
	if (ir / k * k >= il && jr / k * k >= jl)
		upd(ir, jr, 4, d, 1);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> m >> k;
	int is, js; cin >> is >> js, is--, js--;
	int it, jt; cin >> it >> jt, it--, jt--;
	for (int i = 0; i < n; i++)
		cin >> tt, strcpy(aa + i * m, tt);
	for (int ijz = 0; ijz < n * m * 5; ijz++)
		dd[ijz] = n * m;
	head = n * m, upd(is, js, 0, 0, 0);
	while (cnt--) {
		int ijz = qu[head++], i = ijz / 5 / m, j = ijz / 5 % m, z = ijz % 5, d = dd[ijz];
		if (z == 0) {
			for (int h = 0; h < 4; h++) {
				int i_ = i + ddi[h], j_ = j + ddj[h];
				if (0 <= i_ && i_ < n && 0 <= j_ && j_ < m && aa[i_ * m + j_] == '.')
					upd(i_, j_, z, d, 0);
			}
			updsq(i - k, i - 1, j - k + 1, j, d);
			updsq(i - k, i - 1, j, j + k - 1, d);
			updsq(i + 1, i + k, j - k + 1, j, d);
			updsq(i + 1, i + k, j, j + k - 1, d);
			updsq(i - k + 1, i, j - k, j - 1, d);
			updsq(i, i + k - 1, j - k, j - 1, d);
			updsq(i - k + 1, i, j + 1, j + k, d);
			updsq(i, i + k - 1, j + 1, j + k, d);
		} else {
			upd(i, j, 0, d, 0);
			if (z == 1) {
				if (i + 1 < n && i % k)
					upd(i + 1, j, 0, d, 0);
				if (j + 1 < m && j % k)
					upd(i, j + 1, 0, d, 0);
			} else if (z == 2) {
				if (i + 1 < n && i % k)
					upd(i + 1, j, 0, d, 0);
				if (j % k)
					upd(i, j - 1, 0, d, 0);
			} else if (z == 3) {
				if (i % k)
					upd(i - 1, j, 0, d, 0);
				if (j + 1 < m && j % k)
					upd(i, j + 1, 0, d, 0);
			} else {
				if (i % k)
					upd(i - 1, j, 0, d, 0);
				if (j % k)
					upd(i, j - 1, 0, d, 0);
			}
		}
	}
	cout << dd[encode(it, jt, 0)] << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...