Submission #927688

#	Time	Username	Problem	Language	Result	Execution time	Memory
927688		jcelin	Maze (JOI23_ho_t3)	C++14	100 / 100	1012 ms	711488 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 6e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

vi d[MAXN];
vector<bool> mt[MAXN];
int n, m, kv;
vii p[MAXN];


bool izvan(int r, int s){
	if(r < 1 or s < 1 or r > n or s > m) return 1;
	return 0;
}

void expand_na_bijele(int ud){
	queue<ii> q;
	for(auto &x : p[ud]) q.push(x);
	
	while(!q.empty()){
		int r, s;
		tie(r, s) = q.front();
		q.pop();
		for(int k=0; k<4; k++){
			int nr = r + dx[k], ns = s + dy[k];
			if(izvan(nr, ns)) continue;
			if(mt[nr][ns]) continue;
			if(d[nr][ns] != -1) continue;
			d[nr][ns] = ud;
			p[ud].PB({nr, ns});
			q.push({nr, ns});
		}
	}
}

//ud - 1 -> ud
void expand_kvadrat(int ud){
	queue<pair<ii, int>> q;
	for(auto &x : p[ud - 1]) q.push({x, kv - 1});
	while(!q.empty()){
		int r, s, ost;
		tie(r, s) = q.front().X;
		ost = q.front().Y;
		q.pop();
		if(ost == 0) continue;
		for(int k=0; k<8; k++){
			int nr = r + dx[k], ns = s + dy[k];
			if(izvan(nr, ns)) continue;
			if(d[nr][ns] != -1) continue;
			d[nr][ns] = ud;
			p[ud].PB({nr, ns});
			q.push({{nr, ns}, ost - 1});
		}
	}
}

//ud -> ud
void expand_u_4(int ud){
	vii zd = p[ud];
	for(auto &x : p[ud - 1]) zd.PB(x);
	
	for(auto &x : zd){
		for(int k=0; k<4; k++){
			int nr = x.X + dx[k], ns = x.Y + dy[k];
			if(izvan(nr, ns)) continue;
			if(d[nr][ns] != -1) continue;
			d[nr][ns] = ud;
			p[ud].PB({nr, ns});
		}
	}
}

void solve(){
	int sx, sy, ex, ey;
	cin >> n >> m >> kv >> sx >> sy >> ex >> ey;

	for(int i=1; i<=n; i++){
		d[i].resize(m + 1, -1);
		mt[i].resize(m + 1, 1);
		for(int j=1; j<=m; j++){
			char x;
			cin >> x;
			if(x == '.') mt[i][j] = 0;
		}
	}
	
	d[sx][sy] = 0;
	p[0].PB({sx, sy});
	expand_na_bijele(0);
	
	for(int i=1; i<=n+m; i++){
		expand_kvadrat(i);
		expand_u_4(i);
		expand_na_bijele(i);
	}
	
	
	cout << d[ex][ey] << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

• 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