oj.uz

Submission #927666

# Submission time Handle Problem Language Result Execution time Memory
927666 2024-02-15T08:28:58 Z jcelin Maze (JOI23_ho_t3) C++14
0 / 100
 15 ms 63088 KB 
#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 = 1e6 + 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 zadnje, nove;


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 : zadnje) 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;
			nove.PB({nr, ns});
			q.push({nr, ns});
		}
	}
}

void expand_kvadrat(int ud){
	queue<pair<ii, int>> q;
	for(auto &x : zadnje) 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;
			nove.PB({nr, ns});
			q.push({{nr, ns}, ost - 1});
		}
	}
}

void expand_u_4(int ud){
	for(auto &x : zadnje){
		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;
			nove.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;
		}
	}
	
	zadnje.PB({sx, sy});
	d[sx][sy] = 0;
	expand_na_bijele(0);
	for(auto &x : nove) zadnje.PB(x);
	nove.clear();
	
	for(int i=1; i<=n + m; i++){
		expand_kvadrat(i);
		for(auto &x : nove) zadnje.PB(x);
		nove.clear();
		
		expand_u_4(i);
		for(auto &x : nove) zadnje.PB(x);
		nove.clear();
		
		expand_na_bijele(i);
		swap(zadnje, nove);
		nove.clear();
	}
	
	//for(int i=1; i<=n; i++){
		//for(int j=1; j<=m; j++) cout << d[i][j] << " ";
		//cout << "\n";
	//}
	
	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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63064 KB Output is correct
2 Correct 14 ms 63068 KB Output is correct
3 Incorrect 13 ms 63088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63064 KB Output is correct
2 Correct 13 ms 62928 KB Output is correct
3 Correct 13 ms 63084 KB Output is correct
4 Correct 15 ms 63068 KB Output is correct
5 Incorrect 13 ms 62912 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63068 KB Output is correct
2 Correct 13 ms 63080 KB Output is correct
3 Correct 14 ms 63068 KB Output is correct
4 Correct 14 ms 63080 KB Output is correct
5 Correct 13 ms 63068 KB Output is correct
6 Correct 14 ms 63068 KB Output is correct
7 Correct 13 ms 63020 KB Output is correct
8 Incorrect 15 ms 63068 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63064 KB Output is correct
2 Correct 13 ms 62928 KB Output is correct
3 Correct 13 ms 63084 KB Output is correct
4 Correct 15 ms 63068 KB Output is correct
5 Incorrect 13 ms 62912 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63064 KB Output is correct
2 Correct 13 ms 62928 KB Output is correct
3 Correct 13 ms 63084 KB Output is correct
4 Correct 15 ms 63068 KB Output is correct
5 Incorrect 13 ms 62912 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63064 KB Output is correct
2 Correct 14 ms 63068 KB Output is correct
3 Incorrect 13 ms 63088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63064 KB Output is correct
2 Correct 14 ms 63068 KB Output is correct
3 Incorrect 13 ms 63088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63064 KB Output is correct
2 Correct 14 ms 63068 KB Output is correct
3 Incorrect 13 ms 63088 KB Output isn't correct
4 Halted 0 ms 0 KB -