# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
566882 | 2022-05-23T05:18:33 Z | Turkhuu | 밀림 점프 (APIO21_jumps) | C++17 | 0 ms | 0 KB |
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int inf = 1000000; int n; vector<int> a; vector<vector<int>> g; void init(int N, vector<int> H){ n = N; a = H; g.resize(n); for(int i = 0; i < n; i++){ int l = i - 1, r = i + 1; while(l >= 0 && a[l] <= a[i]) l--; while(r < n && a[r] <= a[i]) r++; if(l >= 0) g[i].push_back(l); if(r < n) g[i].push_back(r); ] } int minimum_jumps(int A, int B, int C, int D){ queue<int> q; vector<int> d(n); for(int i = A; i <= B; i++){ d[i] = 0; q.push(i); } while(!q.empty()){ int i = q.front(); q.pop(); if(C <= i && i <= D){ return d[i]; } for(int j : g[i]){ if(d[i] + 1 < d[j]){ d[j] = d[i] + 1; q.push(j); } } } return -1; }