Submission #1105114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105114		Ivo_12	Maze (JOI23_ho_t3)	C++98	100 / 100	336 ms	298452 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define pii pair < int, int >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

const int N = 6e6;
string mat[N];
int n, m, k;
int r1, s1, r2, s2;
vector < vector < pii > > val;
vector < vector < bool > > vis;
pii nul = mp(-1, 0);
deque < pii > dq;
pii spr1[4] = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1)};
pii spr2[8] = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1), mp(1, 1), mp(-1, 1), mp(1, -1), mp(-1, -1)};

void makemat( void ) {
	
	vector < pii > temp;
	vector < bool > tempvis;
	for(int i = 0; i < m; i++) temp.pb(nul);
	for(int i = 0; i < n; i++) val.pb(temp);
	for(int i = 0; i < m; i++) tempvis.pb(0);
	for(int i = 0; i < n; i++) vis.pb(tempvis);
	
}

bool inbounds( int a, int b ) {
	return (a < 0 || b < 0 || a >= n || b >= m) ? 0 : 1;
}

void upis( void ) {
	
	cin >> n >> m >> k;
	cin >> r1 >> s1 >> r2 >> s2;
	r1--; s1--;
	r2--; s2--;
	for(int i = 0; i < n; i++) cin >> mat[i];
	
	return;
}

void solve( void ) {
	
	makemat();
	dq.push_back(mp(r1, s1));
	val[r1][s1] = mp(0, 0);
	pii cur;
	pii curspr;
	while(!dq.empty()) {
		cur = dq.front();
		dq.pop_front();
		if(!vis[cur.F][cur.S]) {
			vis[cur.F][cur.S] = 1;
			
			if(val[cur.F][cur.S].S != 0) {
				for(int i = 0; i < 8; i++) {
					curspr = spr2[i];
					if(inbounds(cur.F + curspr.F, cur.S + curspr.S)) {
						if(val[cur.F + curspr.F][cur.S + curspr.S] == nul) {
							val[cur.F + curspr.F][cur.S + curspr.S] = mp(val[cur.F][cur.S].F, val[cur.F][cur.S].S - 1);
							dq.push_back(mp(cur.F + curspr.F, cur.S + curspr.S));
						}
					}
				}
			}
			
			else {
				for(int i = 0; i < 4; i++) {
					curspr = spr1[i];
					
					if(inbounds(cur.F + curspr.F, cur.S + curspr.S)) {
						if(val[cur.F + curspr.F][cur.S + curspr.S] == nul) {
							
							if(mat[cur.F + curspr.F][cur.S + curspr.S] != '#') {
								val[cur.F + curspr.F][cur.S + curspr.S] = val[cur.F][cur.S];
								dq.push_front(mp(cur.F + curspr.F, cur.S + curspr.S));
							}
							
							else {
								val[cur.F + curspr.F][cur.S + curspr.S] = mp(val[cur.F][cur.S].F + 1, k - 1);
								dq.push_back(mp(cur.F + curspr.F, cur.S + curspr.S));
							}
							
						}	
					}
					
				}
			}
		}
	}
//	for(int i = 0; i < n; i++) {
//		for(int j = 0; j < m; j++) cout << val[i][j].F << " ";
//		cout << "\n";
//	}
//	cout << "\n";
//	for(int i = 0; i < n; i++) {
//		for(int j = 0; j < m; j++) cout << val[i][j].S << " ";
//		cout << "\n";
//	}
//	cout << "\n";
	cout << val[r2][s2].F << "\n";
	
	return;
}

int main( void ) {
	
	FIO;
	upis();
	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