Submission #1148039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148039		fabijan_cikac	Maze (JOI23_ho_t3)	C++20	51 / 100	2094 ms	28652 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;

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;
	
	bool swp = 0;
	if (n > m) swap(n, m), swp = 1;
	
	bool a[n+1][m+1]; pp dist[n+1][m+1];
	FOR(i,1,n) FOR(j,1,m) dist[i][j] = pp(-1,-1);
		
	if (swp){
		char c;
		FOR(i,1,n) FOR(j,1,m){
			cin >> c; a[j][i] = (c == '#');
		}
		swap(n, m); swap(sx, sy); swap(ex, ey);
	}
	else{
		char c;
		FOR(i,1,n) FOR(j,1,m){
			cin >> c; a[i][j] = (c == '#');
		}
	}
	
	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 (dist[x][y] != pp(d1, d2)) continue;
		if (x == ex && y == ey){
			cout << dist[ex][ey].F; return 0;
		}
		
		if (d2 < 0){
			FOR(i,0,7){
				int nx = x + dx[i], ny = y + dy[i];
				if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && (dist[nx][ny] == pp(-1, -1) || dist[nx][ny] > pp(d1, d2 + 1))){
					dist[nx][ny] = pp(d1, d2 + 1);
					q.pf({pp(nx, ny), dist[nx][ny]});
				}
			}
		}
		else{
			FOR(i,0,3){
				int nx = x + dx[i], ny = y + dy[i];
				if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && (dist[nx][ny] == pp(-1,-1) || dist[nx][ny] > pp(d1 + 1, 1 - k))){
					dist[nx][ny] = pp(d1 + 1, 1 - k);
					q.pb({pp(nx, ny), dist[nx][ny]});
				}
				if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !a[nx][ny] && (dist[nx][ny] == pp(-1,-1) || dist[nx][ny] > pp(d1, 0))){
					dist[nx][ny] = pp(d1, 0);
					q.pf({pp(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