제출 #1148022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148022		fabijan_cikac	Maze (JOI23_ho_t3)	C++20	51 / 100	2095 ms	55196 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,j,k) for(int i = j; i <= k; ++i)
#define pb push_back
#define pf push_front
#define pp pair<int, int>
#define F first
#define S second
#define p2 pair<pp, pp>

const int N = 2500;

int n, m, k, sx, sy, ex, ey;
vector<string> a(N);
vector<pp> dist[N];

bool inb(int x, int y){
	return (x >= 1 && x <= n && y >= 1 && y <= m);
}

pp per(int x, int y){
	return pp({x, y});
}

bool eq(pp x, pp y){
	return (x.F == y.F && x.S == y.S);
}

bool grt(pp x, pp y){
	return (x.F > y.F || (x.F == y.F && x.S > y.S));
}

int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> k;
	cin >> sx >> sy >> ex >> ey;
	
	FOR(i,1,min(n,m))
		FOR(j,1,max(n,m)+1)
			a[i].pb('.'), dist[i].pb({-1, -1});
		
	if (n > m){
		FOR(i,1,n) FOR(j,1,m) cin >> a[j][i];
		swap(n, m); swap(sx, sy); swap(ex, ey);
	}
	else{
		FOR(i,1,n) FOR(j,1,m) cin >> a[i][j];
	}
	
	/*FOR(i,1,n){
		FOR(j,1,m) cout << a[i][j];
		cout << '\n';
	}*/
	
	deque<p2> q;
	dist[sx][sy] = {0, 0};
	q.pb({{sx, sy}, {0, 0}});
	
	while (!q.empty()){
		p2 t = q.front(); q.pop_front();
		int x = t.F.F, y = t.F.S, d1 = t.S.F, d2 = t.S.S;
		
		if (!eq(dist[x][y], per(d1, d2))) continue;
		
		if (d2 < 0){
			FOR(i,0,7){
				int nx = x + dx[i], ny = y + dy[i];
				if (inb(nx, ny) && (eq(dist[nx][ny], per(-1, -1)) || grt(dist[nx][ny], per(d1, d2 + 1)))){
					dist[nx][ny] = per(d1, d2 + 1);
					q.pf({per(nx, ny), dist[nx][ny]});
				}
			}
		}
		else{
			FOR(i,0,3){
				int nx = x + dx[i], ny = y + dy[i];
				if (inb(nx, ny) && (eq(dist[nx][ny], per(-1, -1)) || grt(dist[nx][ny], per(d1 + 1, 1 - k)))){
					dist[nx][ny] = per(d1 + 1, 1 - k);
					q.pb({per(nx, ny), dist[nx][ny]});
				}
				if (inb(nx, ny) && a[nx][ny] == '.' && (eq(dist[nx][ny], per(-1, -1)) || grt(dist[nx][ny], per(d1, 0)))){
					dist[nx][ny] = per(d1, 0);
					q.pf({per(nx, ny), dist[nx][ny]});
				}
			}
		}
	}
	
	cout << dist[ex][ey].F;
	
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6