Submission #1144768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144768		fabijan_cikac	Maze (JOI23_ho_t3)	C++20	0 / 100	1 ms	584 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define pp pair<int, int>
#define F first
#define S second

const int N = 1010;
const int INF = 1e9;

int n, m, k;
int X1, Y1, X2, Y2;
char a[N][N];
int dist[N][N];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool bio[N][N];

queue<pp> q;
bool inb(int x, int y){
	return (x >= 0 && x < n && y >= 0 && y < m);
}

void fill(int l1, int l2, int r1, int r2, int x){
	for (int i = l1; i <= l2; ++i)
		for (int j = r1; j <= r2; ++j){
			if (!inb(i, j)) continue;
			dist[i][j] = min(dist[i][j], x);
			if (!bio[i][j]) q.push({i, j}), bio[i][j] = 1;
		}
}

int main(){
	cin >> n >> m >> k;
	cin >> X1 >> Y1 >> X2 >> Y2;
	--X1, --Y1, --X2, --Y2;
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> a[i][j];
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			dist[i][j] = INF;
	
	dist[X1][Y1] = 0;
	vector<pair<int, pp> > v;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			v.pb({abs(i - X1) + abs(j - Y1), {i, j}});
	sort(v.begin(), v.end());
	
	q.push({X1, Y1}); bio[X1][Y1] = 1;
	while (!q.empty()){
		int x = q.front().F, y = q.front().S; q.pop();
		for (int i = 0; i < 4; ++i){
			if (inb(x + dx[i], y + dy[i]) && a[x + dx[i]][y + dy[i]] == '.'){
				dist[x + dx[i]][y + dy[i]] = min(dist[x + dx[i]][y + dy[i]], dist[x][y]);
				if (!bio[x + dx[i]][y + dy[i]]) q.push({x + dx[i], y + dy[i]}), bio[x + dx[i]][y + dy[i]] = 1;
			}
		}
		
		fill(x - k + 1, x + k - 1, y - k, y + k, dist[x][y] + 1);
		fill(x - k, x + k, y - k + 1, y + k - 1, dist[x][y] + 1);
	}
	
	cout << dist[X2][Y2];
	
	return 0;
}

• Subtask 1: 0 / 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